如何反转链接列表？

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