206. Reverse Linked List.md

206. 反转链表

反转一个单链表。

示例:

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

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解法一

//时间复杂度O(n), 空间复杂度O(1)
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *p = nullptr, *c = head, *n;
        while(c != nullptr) {
            n = c->next;
            c->next = p;
            p = c;
            c = n;
        }
        return p;
    }
};

解法二

//时间复杂度O(n), 空间复杂度O(n)
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;//链表结点数小于2时返回
        ListNode *first = head->next;//保存新链表尾
        head->next = nullptr;//head修改next指针
        ListNode *last = reverseList(first);//反转子链表, 并返回新链表头
        first->next = head;//子链表尾加上head
        return last;//返回新链表头
    }
};

解法一 常规解法，用三个变量p、c、n分别记下前一个、当前、下一个结点，循环地将当前结点的next指向前结点，再将三个指针向后移动。最后返回p（它是最后一个结点，也是新链表的第一个结点）。 解法二 递归法：

1. 每次抽出第一个结点head，记下第二个结点first；
2. 然后将第二个结点开始的后续链表反转，并返回反转后的第一个结点last；
3. 再将新链表尾元素first后，加上head；
4. 递归地进行，终止条件是当前结点的next指针为空。

2019/04/28 18:24