如何撤消链表？

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现在是current 。 最后current变得forward ？

我似乎无法掌握这一点以及它的逆转方式。 有人可以解释这是如何工作的？

Answer 1

Answer 2

您可以迭代地反转列表，并始终使区间[head，previous]中的列表正确反转（因此current是第一个未正确设置其链接的节点）。 在每个步骤中，您执行以下操作：

• 您记住当前的下一个节点，以便您可以继续使用它
• 您将当前的链接设置为指向上一个，如果您考虑它，这是正确的方向
• 您将之前的更改为当前，因为现在当前也正确设置了其链接
• 您将没有正确链接集的第一个节点更改为第一步中重新编号的节点

如果您为所有可以certificate的节点执行此操作（例如，使用归纳）。 该列表将被正确颠倒。

Answer 3

代码只是遍历列表并反转链接，直到它到达前一个尾部，它将作为新头返回。

之前：

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

后：

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

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通道算法。

  (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: EBCDA when j=1, swap(1, 3) //post swap state: EDCBA 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: DBCA when j=1, swap(1, 2) //post swap state: DCBA 

• 交换仅适用于数据，而不适用于指针，可能会遗漏任何健全性检查，但您明白了。

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