link list反轉(invert)

小弟剛開始學link list
看到一個習題是單純反轉link list
有個疑問 為什麼我不能輸入什麼就馬上輸出
這樣不是會更快嗎?
但是用online judge的系統卻沒辦法
是有什麼測資會爆炸嗎?


那我該如何從link list下手
如何讓1 2 3 4 5讀檔進去
link list 反轉後
變成5 4 3 2 1
求各位大大開導
...

瀏覽完整內容，請先 註冊 或 登入會員

reverse 在數學上的意義用 Agda 表達是：

1. data ℕ : Set where
   
2.   zero : ℕ
   
3.   suc  : ℕ → ℕ
   
4. 
   
5. data Vect {l} (A : Set l) : ℕ → Set l where
   
6.   []  : Vect A zero
   
7.   _∷_ : ∀ {n} → A → Vect A n → Vect A (suc n)
   
8. 
   
9. insert : ∀ {l n} {A : Set l} → A → Vect A n → Vect A (suc n)
   
10. insert x []       = x ∷ []
    
11. insert x (y ∷ ys) = y ∷ (insert x ys)
    
12. 
    
13. reverse : ∀ {l n} {A : Set l} → Vect A n → Vect A n
    
14. reverse (x ∷ xs) = insert x (reverse xs)
    
15. reverse whatever = whatever

複製代碼

用 C++ 來實作的話，SGI 版本的 stl 的 std::list 對 reverse 的實作大約是像這樣(我大約寫的，不一定完全相同)：

1. void
   
2. M_reverse_() noexcept
   
3. {
   
4.   list_node_base_* tmp__ = this;
   
5.   do
   
6.     {
   
7.       std::swap(tmp__->M_next_, tmp__->M_prev_);
   
8.       tmp__ = tmp__->M_prev_;
   
9.     }
   
10.   while (tmp__ != this);
    
11. }
    
12. 
    
13. void
    
14. reverse() noexcept
    
15. { this->M_impl_.M_node_.M_reverse_(); }

複製代碼

...

瀏覽完整內容，請先 註冊 或 登入會員

hf387

可以一開始就反著連
新的 Node 往前一個 Node 連
Head 指向新的 Node

簡單寫大概這樣吧(沒驗證)

1. Node* mHead = NULL;
   
2. 
   
3. Node* mNode = new Node;
   
4. mNode->next = mHead;
   
5. mHead = mNode;

複製代碼

coal511464

hi, 你可以學學stl 裡面有很多好用的容器
自己做太累的 不然網路上也有很多範例

你可以用 doubly linked list 偷吃步，不過既然會考你 link list 反轉，應該是要考你如何將單向 linked list 反轉，你需要同時用三個變數紀錄前一個、後一個、和現在的節點，演算法如下：

1. static wznode *
   
2. wz_invert_node(wznode * node) { /* node must not be NULL */
   
3.   wznode * root;
   
4.   wznode * c = node; /* c => child */
   
5.   wznode * n = c->parent; /* n => node */
   
6.   wznode * p; /* p => parent */
   
7.   for (;;) {
   
8.     if (n == NULL) {
   
9.       root = c;
   
10.       break;
    
11.     }
    
12.     p = n->parent;
    
13.     n->parent = c;
    
14.     if (p == NULL) {
    
15.       root = n;
    
16.       break;
    
17.     }
    
18.     c = n;
    
19.     n = p;
    
20.   }
    
21.   node->parent = NULL;
    
22.   return root;
    
23. }

複製代碼

以這個例子說明，每個 node 都有自己的父節點，利用各自的父節點將節點們連接成一個單向 linked list，最頂端的父節點的父節點是 NULL，相當於單向 linked list 的尾巴，最底端的子節點相當於單向 linked list 的頭，這個函數將最底端的子節點作為輸入，然後將整條單向 linked list 反轉後回傳原本最頂端的父節點，也就是新的單向 linked list 的頭...

瀏覽完整內容，請先 註冊 或 登入會員