如何反轉鏈接列表？

Question

Node reverse(Node head) { 
    Node previous = null; 
    Node current = head; 
    Node forward; 

    while (current != null) { 
     forward = current.next; 
     current.next = previous; 
     previous = current; 
     current = forward; 
    } 

    return previous; 
} 

它究竟如何反轉列表？我知道它首先將第二個節點設置爲forward。然後它說current.next等於null節點previous。然後它說previous現在是current。最後current變成forward？

我似乎無法理解這一點，以及它如何逆轉。有人可以解釋這是如何工作的？

Answer 1

您可以迭代地反轉列表，並始終在正確反轉的區間[head，previous]中設置列表（因此current是第一個鏈接設置不正確的節點）。在每個步驟中，您做到以下幾點：

• 你還記得當前的下一個節點，以便您可以繼續從它
• 您設定的當前的鏈接是指向以前，也就是如果你的正確方向想想
• 您更改以前是當前，因爲現在目前也有它的鏈接設置正確
• 您更改不HAE其鏈接正確設置是一個在第一步remebered的第一個節點

如果你這樣做了所有可以證明的節點（例如歸納）。該名單將被正確顛倒。

Answer 2

該代碼只是遍歷列表並倒轉鏈接，直到它到達前一個尾部，它將作爲新頭部返回。

前：

Node 1 (Head) -> Node 2 -> Node 3 -> Node 4 (Tail) -> null 

後：

null <- Node 1 (Tail) <- Node 2 <- Node 3 <- Node 4 (Head) 

Answer 3

Answer 4

public Node getLastNode() 
{ 
    if(next != null) 
     return next.getLastNode(); 
    else 
     return this; 
} 

public Node reverse(Node source) 
{ 
    Node reversed = source.getLastNode(); 
    Node cursor = source; 

    while(cursor != reversed) 
    { 
     reversed.addNodeAfter(cursor.getInfo()); 
     cursor = cursor.getNodeAfter(); 
    } 

    source = reversed; 
    return source; 
} 

Answer 5

我把它叫做「採摘櫻桃」。這個想法是儘量減少交換次數。交換髮生在遠近指標和遠指數之間。它是一個2-pass算法。

(Odd length) A -> B -> C -> D -> E 
    (Even length) A -> B -> C -> D 

    Pre-Condition: N >= 2 

    Pass 1: Count N, the number of elements 

    Pass 2: 
      for(j=0 -> j<= (N/2 -1)) 
      { 
       swap(j, (N-1)-j) 
      } 

實施例1：

For above Odd length list, N = 5 and there will be two swaps 

     when j=0, swap(0, 4) //post swap state: E B C D A 
     when j=1, swap(1, 3) //post swap state: E D C B A 


    The mid point for odd length lists remains intact. 

實施例2：

For above Even length list, N = 4 and there will be two swaps 

     when j=0, swap(0, 3) //post swap state: D B C A 
     when j=1, swap(1, 2) //post swap state: D C B A 

• 交換來實現適用於數據只，而不是指針，可能有遺漏的健全性檢查，但你明白了。

Answer 6

倒車使用迭代

current = head //point current pointer to head of the linked list 

while(current != NULL) 
{ 
forward = current->link; //point to the next node 
fforward = forward->link; //point the next node to next node 
fforward->link = forward;//1->2->3,,,,,,,,,this will point node 3 to node 2 
forward->link = current; //this will point node 2 to node 1 
if(current == head) 
current->link = NULL;// if current pointer is head pointer it should point to NULL while reversing 

current = current->link; //traversing the list 
} 
head = current; //make current pointer the head pointer 

Answer 7

list_t *reverse(list_t *a) 
    { 
    list_t *progress = NULL; 
    while(a) 
    { 
     list_t *b; //b is only a temporary variable (don't bother focusing on it) 
     b = a->next; 
     a->next = progress; //because a->next is assigned to another value, we must first save a->next to a different variable (to be able to use it later) 
     progress = a; //progress is initially NULL (so a->next = NULL (because it is the new last element in the list)) 
     a = b; //we set a to b (the value we saved earlier, what a->next was before it became NULL) 
     /* 
     now, at next iteration, progress will equal a, and a will equal b. 
     so, when I assign a->next = progress, I really say, b->next = a. 
     and so what we get is: b->a->NULL. 
     Maybe that gives you an idea of the picture? 
     What is important here is: 
      progress = a 
     and 
      a = b 
     Because that determines what a->next will equal: 
      c->b->a->0 
     a's next is set to 0 
     b's next is set to a 
     c's next is set to b 
     */ 
    } 
    return progress; 
    } 

Answer 8

基本思想單鏈表是從第一清單中分離的頭節點並將其附加到一個第二列表的頭部。繼續重複，直到第一個列表爲空。

僞代碼：

function reverseList(List X) RETURNS List 
    Y = null 
    WHILE X <> null 
     t = X.next 
     X.next = Y 
     Y = X 
     X = t 
    ENDWHILE 
    RETURN Y 
ENDfunction 

如果你想保留原始列表不受干擾，那麼你可以通過使用一個輔助函數的遞歸編寫一個複製版本。

function reverseList(List X) RETURNS List 
    RETURN reverseListAux(X, null) 
ENDfunction 

function reverseListAux(List X, List Y) RETURNS List 
    IF X = null THEN 
     RETURN Y 
    ELSE 
     RETURN reverseListAux(X.next, makeNode(X.data, Y)) 
ENDfunction 

請注意，輔助函數是尾遞歸。這意味着您可以使用迭代創建複製反轉。

function reverseList(List X) RETURNS List 
    Y = null 
    WHILE X <> null 
    Y = makeNode(x.data, Y) 
    X = X.next 
    ENDWHILE 
    RETURN Y 
ENDfunction