反向单链表

Question

我有下面的程序来反转单链表中的元素。我不能让它工作。我使用了简单的变量交换技术来交换节点，但当我打印时，它不会超出第一个节点。

public static void reverseLinkedList(Node head) {
    Node current = head;
    Node temp = null;
    while (current != null && current.next != null) {
        temp = current;
        current = current.next;
        current.next = temp;
    }
}
public static void printData(Node head) {
    Node currentNode = head;
    while (true) {
        System.out.println(currentNode.data);
        if (currentNode.next != null) {
            currentNode = currentNode.next;
        } else {
            break;
        }
    }
}

Answer 1

我更喜欢在函数之后返回head节点。使事情简单

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

或者，您可以选择更简单的递归版本

Node reverse(Node head) { 
    if(head == null) { 
        return head; 
    } 

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

    Node newHeadNode = reverse(head.next); 

    head.next.next = head; 
    head.next = null; 
    return newHeadNode; 
}