Java反转单向链表

Question

有人能告诉我为什么我的代码不起作用吗？我想在Java中反转一个单向链表：这是该方法（不正确工作的方法）：

public void reverseList(){
    Node before = null;
    Node tmp = head;
    Node next = tmp.next;
    while(tmp != null){
      if(next == null)
         return;
      tmp.next = before;
      before = tmp;
      tmp = next;
      next = next.next;
    }
}

这是 Node 类:

public class Node{
   public int data;
   public Node next;
   public Node(int data, Node next){
      this.data = data;
      this.next = next;
   }
}

输入 4->3->2->1 后，我得到输出 4。我进行了调试并发现指针被正确设置，但仍然不明白为什么只输出了 4。

- sammy333

---

完整的逐步解释和动画演示。单次迭代的最佳解决方案。 - Anindya Sankar Dasgupta

Answer 1

Node next = tmp.next;
while(tmp != null){

当 tmp == null 时会发生什么？

你几乎已经懂了，不过还有一点点差距。

Node before = null;
Node tmp = head;
while (tmp != null) {
    Node next = tmp.next;
    tmp.next = before;
    before = tmp;
    tmp = next;
}
head = before;

或者使用更友善（？）的命名：

Node reversedPart = null;
Node current = head;
while (current != null) {
    Node next = current.next;
    current.next = reversedPart;
    reversedPart = current;
    current = next;
}
head = reversedPart;

ASCII 艺术：

        <__<__<__ __ : reversedPart    : head
                 (__)__ __ __
head :   current:      >  >  >

- Joop Eggen

---

嘿，我们不能把“Node next = current.next”这一行放在while循环外面吗？然后只在while循环里面放“next = current.next”？就像对于reversedPart和current一样，我们只需要在while循环外面放置“Node next = null”？ - satnam

@Satnamxv63，感谢您的想法，但在Java中，在循环内部声明变量与在外部声明变量相比没有任何惩罚。只有一个变量槽被保留给“next”。 - Joop Eggen

@dharam 不错；只有动画 gif 或类似的东西才能超越它。 - Joop Eggen

@JoopEggen 谢谢。关于动态GIF，下次会注意的。 - dharam

非常好的解决方案！谢谢。 - Roberto Rodriguez

完整的逐步解释和动画演示。单次迭代的最佳解决方案。 - Anindya Sankar Dasgupta

Answer 2

public Node<E> reverseList(Node<E> node) {
    if (node == null || node.next == null) {
        return node;
    }
    Node<E> currentNode = node;
    Node<E> previousNode = null;
    Node<E> nextNode = null;

    while (currentNode != null) {
        nextNode = currentNode.next;
        currentNode.next = previousNode;
        previousNode = currentNode;
        currentNode = nextNode;
    }
    return previousNode;
}

- Ranjeet

---

完整的逐步解释和动画演示。单次迭代的最佳解决方案。 - Anindya Sankar Dasgupta

Answer 3

反转链表的方法如下：

反转方法

public void reverseList() {
    Node<E> curr = head;
    Node<E> pre = null;
    Node<E> incoming = null;

    while(curr != null) {
        incoming = curr.next;   // store incoming item

        curr.next = pre;        // swap nodes
        pre = curr;             // increment also pre

        curr = incoming;        // increment current
    }

    head = pre; // pre is the latest item where
                // curr is null
}

反转列表需要三个引用: pre、curr和incoming

...      pre     curr    incoming
... --> (n-1) --> (n) --> (n+1) --> ...

为了反转一个节点，你需要存储前一个元素，以便可以使用简单的语句；

curr.next = pre;

要反转当前元素的方向。但是，为了遍历整个列表，在执行上述语句之前必须存储传入的元素，因为在反转当前元素的下一个引用时，您不再知道传入的元素，这就是为什么需要第三个引用。

演示代码如下：

LinkedList示例类

public class LinkedList<E> {

    protected Node<E> head;

    public LinkedList() {
        head = null;
    }

    public LinkedList(E[] list) {
        this();
        addAll(list);
    }

    public void addAll(E[] list) {
        for(int i = 0; i < list.length; i++)
            add(list[i]);
    }

    public void add(E e) {
        if(head == null)
            head = new Node<E>(e);
        else {
            Node<E> temp = head;

            while(temp.next != null)
                temp = temp.next;

            temp.next = new Node<E>(e);
        }
    }

    public void reverseList() {
        Node<E> curr = head;
        Node<E> pre = null;
        Node<E> incoming = null;

        while(curr != null) {
            incoming = curr.next;   // store incoming item

            curr.next = pre;        // swap nodes
            pre = curr;             // increment also pre

            curr = incoming;        // increment current
        }

        head = pre; // pre is the latest item where
                    // curr is null
    }

    public void printList() {
        Node<E> temp = head;

        System.out.print("List: ");
        while(temp != null) {
            System.out.print(temp + " ");
            temp = temp.next;
        }

        System.out.println();
    }

    public static class Node<E> {

        protected E e;
        protected Node<E> next;

        public Node(E e) {
            this.e = e;
            this.next = null;
        }

        @Override
        public String toString() {
            return e.toString();
        }

    }

}

测试代码

public class ReverseLinkedList {

    public static void main(String[] args) {
        Integer[] list = { 4, 3, 2, 1 };

        LinkedList<Integer> linkedList = new LinkedList<Integer>(list);

        linkedList.printList();
        linkedList.reverseList();
        linkedList.printList();
    }

}

输出

List: 4 3 2 1 
List: 1 2 3 4 

- Levent Divilioglu

---

一个非常好而且清晰的回答！值得更多的投票。 - KKlalala

完整的逐步解释和动画演示。在单次迭代中获得最佳解决方案。 - Anindya Sankar Dasgupta

Answer 4

如果这不是作业，而是有意手动执行此操作，那么我建议使用。

Collections.reverse(list);

Collections.reverse()方法返回void类型，在调用之后你的列表将被颠倒。

- Oliver Hausler

---

请问为什么是 -1？Collections.reverse() 会将列表反转，这不就是问题的要求吗？ - Oliver Hausler

问题中提供的Node类不是List类型，因此不能作为Collections.reverse(List<T> list)方法的参数。请注意，这是一个单向链表，并且不使用Java的LinkedList实现。如果问题尝试反转例如LinkedList对象，则您的答案将是正确的。 - Petros P

Answer 5

我们可以有三个节点：前一个、当前和后一个。

public void reverseLinkedlist()
{
    /*
     * Have three nodes i.e previousNode,currentNode and nextNode
 When currentNode is starting node, then previousNode will be null
 Assign currentNode.next to previousNode to reverse the link.
 In each iteration move currentNode and previousNode by  1 node.
     */

    Node previousNode = null;
    Node currentNode = head;
    while (currentNode != null) 
    {
        Node nextNode = currentNode.next;
        currentNode.next = previousNode;
        previousNode = currentNode;
        currentNode = nextNode;
    }
    head = previousNode;
}

- Sathesh

Answer 6

public void reverse() {
    Node prev = null; Node current = head; Node next = current.next;
    while(current.next != null) {
        current.next = prev;
        prev = current;
        current = next;
        next = current.next;
    }
    current.next = prev;
    head = current;
}

- Sean Paul

Answer 7

    // Java program for reversing the linked list
    class LinkedList {

        static Node head;

        static class Node {

            int data;
            Node next;

            Node(int d) {
                data = d;
                next = null;
            }
        }

      //  Function to reverse the linked list 
        Node reverse(Node node) {
            Node prev = null;
            Node current = node;
            Node next = null;
            while (current != null) {
                next = current.next;
                current.next = prev;
                prev = current;
                current = next;
            }
            node = prev;
            return node;
        }




        // prints content of double linked list
        void printList(Node node) {
            while (node != null) {
                System.out.print(node.data + " ");
                node = node.next;
            }
        }


        public static void main(String[] args) {
            LinkedList list = new LinkedList();
            list.head = new Node(85);
            list.head.next = new Node(15);
            list.head.next.next = new Node(4);
            list.head.next.next.next = new Node(20);

            System.out.println("Given Linked list");
            list.printList(head);
            head = list.reverse(head);
            System.out.println("");
            System.out.println("Reversed linked list ");
            list.printList(head);
        }
    }


OUTPUT: -

Given Linked list
85 15 4 20 
Reversed linked list 
20 4 15 85 

- Saurabh Prakash

---

请解释一下你的答案在做什么以及它是如何做到的。 - Barkermn01

Answer 8

我不理解...为什么不这样做：

？

private LinkedList reverseLinkedList(LinkedList originalList){
    LinkedList reversedList = new LinkedList<>();

    for(int i=0 ; i<originalList.size() ; i++){
        reversedList.add(0, originalList.get(i));
    }

    return reversedList;
}

我觉得这更容易。

- Manov

---

因为这个问题涉及到单向链表，而你的解决方案使用了Java的LinkedList，它有许多基本单向链表没有的函数。例如，如果Java没有提供get(index)方法，那么你的代码将无法实现。在这种情况下，Node类并没有这样的方法。 - Petros P

你提供的代码不够内存高效，因为它更容易且浪费了两倍的内存。而且你甚至不知道垃圾回收器将何时释放未使用的旧列表。 - Levent Divilioglu

Answer 9

一个更优雅的解决方案是使用递归。

void ReverseList(ListNode current, ListNode previous) {
            if(current.Next != null) 
            {
                ReverseList(current.Next, current);
                ListNode temp = current.Next;
                temp.Next = current;
                current.Next = previous;
            }
        }

- Shayno

---

在一个非常大的列表中，这段代码会导致堆栈溢出。使用递归而不是迭代解决方案是一个糟糕的选择。 - Levent Divilioglu

Answer 10

Node reverse_rec(Node start) {
    if (start == null || start -> next == null) {
       return start;
    }

    Node new_start = reverse(start->next);
    start->next->next = start;
    start->next = null;
    return new_start;
}


Node reverse(Node start) {
    Node cur = start;
    Node bef = null;

    while (cur != null) {
       Node nex = cur.next;
       cur.next = bef;
       bef = cur;
       cur = nex;
    }
    return bef;
}

- user2547616