反向单链表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.

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

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

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) --> ...

要扭转一个节点,您可以选择存储前 vious元素,这样就可以使用简单stament;

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 

Answer 4

如果这不是作业,而你是故意"手动"这样做,那么我建议使用

Collections.reverse(list);

Collections.reverse()返回void,调用后您的列表会反转.