206. Reverse Linked List

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?

---

本题要将一个链表反转。简单题，分为迭代法和递归法，迭代法比较容易想到，依次把链表当前的头结点断开，然后用头插法插到新链表的开头。算法如下：

class Solution {
public:
    ListNode* reverseList(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode* new_head = new ListNode(0);
        while (head != NULL) {
            ListNode* prior = head;
            head = head->next;
            prior->next = new_head->next;
            new_head->next = prior;
        }
        return new_head->next;
    }
};

本代码提交AC，用时9MS。 本题还要求实现递归法。比如链表1->2->3->4，递归的时候把头结点1断开，假设我们能得到2->3->4的反转链表4->3->2，则还需要把1接在之前反转链表的末尾。但是我们得到的4->3->2只返回了头结点，怎么得到尾节点2呢，唯一的方法就是开始我们不断开1，这样我们就可以用1->next得到2，然后把1->next->next=1，最后把1->next置为NULL。算法如下：

class Solution {
public:
    ListNode* reverseList(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode* reversed_list = reverseList(head->next);
        head->next->next = head; // 重点
        head->next = NULL;
        return reversed_list;
    }
};

本代码提交AC，用时6MS。

二刷。更好理解的递归方法，比如链表1->2->3->4，先把2->3->4逆序变成4->3->2，注意此时1后面还是连着2，也就是说我们可以通过1找到2->3->4逆序的尾巴，然后把1接到尾巴即可。完整代码如下：

class Solution {
public:
	ListNode* reverseList(ListNode* head) {
		if (head == NULL)return NULL;
		if (head->next == NULL)return head;
		ListNode* tail = head->next;
		ListNode *rev_head = reverseList(head->next);
		tail->next = head;
		head->next = NULL;
		return rev_head;
	}
};

本代码提交AC，用时4MS。