LeetCode 206. Reverse Linked List

[Woodyiiiiiii]

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?

---

这是一道非常基础的链表题目——链表反转。
我起初一开始的就两种解法，都是迭代(iteratively)法：

// 三指针法
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode node = head;
        ListNode pre = null, next = null;
        while (node != null) {
            next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }
}

// 头插法
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode headPro = new ListNode(0);
        headPro.next = head;
        ListNode pre = head, node = head.next, next = null;
        while (node != null) {
            next = node.next;
            node.next = headPro.next;
            headPro.next = node;
            pre.next = next;
            node = next;
        }
        return headPro.next;
    }
}

还有递归(recursively)法。
其主要思想是递归到倒数第二个节点，将倒数第一个节点指向倒数第二个节点，后者指向空，返回倒数第一个节点。以此回溯，倒数第三个节点会指向空，同时一个反转的子链表末尾是倒数第三个节点。总结来说，就是返回的是末尾节点，其余节点的逻辑是让它的下一个节点指向它，它本身指向null。应用了回溯的思想。

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

---

参考资料：

• https://leetcode.com/problems/reverse-linked-list/