反向单向链表 Java

java singly-linked-list

2022-09-01 07:56:55

有人可以告诉我为什么我的代码dosent工作吗？我想在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。

答案 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:      >  >  >

答案 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;
}