[Java算法系列教程]-单链表反转

要求很简单，输入一个链表，反转链表后，输出新的链表。

首先定义Node：

public static class Node {
    public int value;
    public Node next;

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

递归法

递归法是从最后一个Node开始，在弹栈的过程中将指针顺序置换

public Node reverse(Node head) {
    if (head == null || head.next == null)
        return head;
    Node temp = head.next;
    Node newHead = reverse(head.next);
    temp.next = head;
    head.next = null;
    return newHead;
}

遍历法

遍历法就是在链表遍历的过程中将指针顺序置换

public static Node reverse(Node node) {
    Node pre = null;
    Node next = null;
    while (node != null) {
        next = node.next;
        node.next = pre;
        pre = node;
        node = next;
    }
    return pre;
}