如何反转链表？

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。然后它说先前现在是当前。最后当前变成前进？

我似乎无法理解这一点以及它是如何逆转的。有人可以解释一下这是如何工作的吗？

Answer 1

Answer 2

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

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

如果您对所有节点都这样做，则可以证明（例如使用归纳法）该列表将被正确颠倒。

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

最简单的思考方法是这样思考：

1. 首先将链表的头添加到一个新的链表中。
2. 继续迭代原始链表并继续添加新链表头部之前的节点。

图表：

最初：

Original List -> 1 2 3 4 5
New List -> null

第一次迭代

Original List -> 1 2 3 4 5
New List -> 1->null [head shifted to left, now newHead contains 1 and points to null]

第二次迭代

Original List -> 1 2 3 4 5
New List -> 2-> 1->null [head shifted to left, now newHead contains 2 and points to next node which is 1]

第三次迭代

Original List -> 1 2 3 4 5
New List ->3 -> 2-> 1->null [head shifted to left, now newHead contains 2 and points to next node which is 1]

现在一直循环到最后。所以最后新列表变成：

  New List->  5 -> 4 -> 3 -> 2 -> 1 -> null

相同的代码应该是这样的（使其易于理解）：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

public ListNode reverseList(ListNode head) {
    if(head == null) {
        return null;
    }

    if(head.next == null) {
        return head;
    }

    ListNode current = head;
    ListNode previous = new ListNode(head.val);
    previous.next = null;

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

    return previous;
}

private ListNode addBeforeHead(ListNode node, ListNode head) {
    if (node == null) return null;
    ListNode temp = new ListNode(node.val);

    temp.next = head;
    head = temp;

    return head;
}

Answer 5

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 6

我称之为“樱桃采摘”。这个想法是尽量减少交换次数。交换发生在近索引和远索引之间。这是一个 twp-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 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 the 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

Answer 9

使用迭代反转单链表：

current = head // Point the current pointer to the 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 the current pointer is the head pointer it should point to NULL while reversing

    current = current->link; // Traversing the list
}
head = current; // Make the current pointer the head pointer

Answer 10

单链表反转函数的实现：

struct Node
{
    int data;
    struct Node* link;
}

Node* head = NULL;

void reverseList()
{
    Node* previous, *current, *next;
    previous = NULL;
    current = head;

    while(current != NULL)
    {
        next = current-> link;
        current->link = previous;
        previous = current;
        current = next;
    }

    head = previous;
}

Answer 11

这是一个简单的函数来反转单链表

// Defining Node structure


public class Node {
int value;
Node next;


public Node(int val) {
    
    this.value=val;
}

}

public LinkedList reverse(LinkedList list) {
    
    if(list==null) {
        
        return list;
    }
    
    Node current=list.head;
    Node previous=null;
    Node next;
    
    while(current!=null) {
        
        next=current.next;
        
        current.next=previous;
        
        previous=current;
        
        current=next;
        
    }
    
    list.head=previous;
    
    return list;
    
    
    
    
}

为了更好地理解，你可以观看这个视频 https://youtu .be/6SYVz-pnVwg

Answer 12

如果你想使用递归：

         class Solution {

         ListNode root=null;

         ListNode helper(ListNode head)
         {
             if (head.next==null)
             {  root= head;
                 return head;}

             helper (head.next).next=head;
             head.next=null;

             return head;
         }


         public ListNode reverseList(ListNode head) {
             if (head==null)
             {
                 return head;
             }
             helper(head);
             return  root;

         }
     }

Answer 13

public void reverseOrder() {
    if(head == null) {
        System.out.println("list is empty");
    }
    else {
    Node cn = head;
    int count = 0;
    while (cn != null) {
        count++;
        cn = cn.next;
    }
    Node temp;
    for(int i = 1; i<=count; i++) {
        temp = head;
        for(int j = i; j<count; j++) {
            temp = temp.next;
        }
        System.out.print(temp.data+" ->");
    }
    System.out.print("null");
}
}