剑指 Offer 24. 反转链表

题目

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：
0 <= 节点个数 <= 5000

第一次

将链表压栈出栈。

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        Stack<ListNode> stack = new Stack<>();
        ListNode node = head;
        while(node != null) {
            stack.push(node);
            node = node.next;
        }
        ListNode root = stack.pop();
        node = root;
        while(!stack.isEmpty()) {
            node.next = stack.pop();
            node = node.next;
        }
        // 注意断开
        node.next = null;
        return root;
    }
}

第二次

使用遍历将后一个指向前一个

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head;
        while(cur != null) {
            // 缓存下一个节点，以便 while 继续
            ListNode node = cur.next;
           // 将当前节点指向上一个节点
            cur.next = pre;
           // 替换
            pre = cur;
            cur = node;
        }
        return pre;
    }
}

第三次

使用递归，模拟栈操作

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        ListNode node = reverseList(head.next);
        if (node == null) {
            return head;
        } else {
            // 换指
            head.next.next = head;
            head.next = null;
            return node;
        }
    }
}