2020-02-16 刷题 3（链表）

21 合并两个有序链表

标签：归并，双指针，链表
解题思路类似于二路归并算法，采用双指针法，将其中一个链表作为待合并链表(l2)，合并到另一个链表(l1)上。需要注意链表为空的情况。

给l1添加一个哨兵头节点，第一个指针p一直指向当前比较位置的前驱。第二个指针q指向l2的当前比较位置。从左到右扫描l1，直到找到第一个大于q的节点，也就是p的后继，将q插在p之后。

代码：

time: 84.27%, memory: 74.10%
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // mind the empty list
        ListNode *h1 = new ListNode(0);
        h1 -> next = l1;
        ListNode *p = h1, *q = l2;
        while((p -> next) && q){
            while((p -> next) && q && ((p -> next) -> val) <= (q -> val)){
                p = p -> next;
            }
            while((p -> next) && q && ((p -> next) -> val) > (q -> val)){
                ListNode *tmp = p -> next;
                p -> next = q;
                q = q -> next;
                (p -> next) -> next = tmp;
                p = p -> next;
            }
        }
        while(q){
            p -> next = q;
            p = p -> next;
            q = q -> next;
        }
        return h1 -> next;
    }
};

234 回文链表

判断一个单向链表是不是回文，首先想到的解法是，将链表复制一份并且翻转，如果原链表与翻转链表完全相同，则链表是回文链表。特别需要注意链表为空的情况。
标签：链表，双指针（快慢指针找中点）
时间复杂度：O(n), 空间复杂度：O(n)
代码：

time: 71.82%, memory: 5.07%
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // reverse
        if(!head) return true;
        ListNode *p = head -> next, *q = new ListNode(head -> val);
        while(p){
            ListNode *tmp = new ListNode(p -> val);
            tmp -> next = q;
            q = tmp;
            p = p -> next;
        }
        // compare
        ListNode *head2 = q;
        p = head;
        bool isSym = true;
        while(p && q){
            if(p -> val != q -> val) {
                isSym = false;
                break;
            }
            p = p -> next;
            q = q -> next;
        }
      // 删除辅助链表
        while(head2){
            ListNode *tmp = head2;
            head2 = head2 -> next;
            delete tmp;
        }
        return isSym;
    }
};

不过，上面的解法空间复杂度是O(n). 题目的拓展要求是，采用O(1)的复杂度，所以又想了一种常数空间复杂度的方法，先找到链表的中点，然后把链表的后半部分翻转，最后比较链表的前半部分和后半部分。

这里学到一个骚操作（可能也不是很骚），我开始用了一种非常笨的办法来找链表中点，就是先从左到右统计一下，再从左走到中点，是不是非常笨非常笨。看了题解之后发现，快慢指针法：可以设置两个指针，一个快指针，一个慢指针，两个指针都从链表头出发，快指针每次走两步，慢指针每次走一步，快指针走到链表尾部的时候，慢指针恰好走到中点。

代码：

time: 42.62%, memory: 49.33%
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // 双指针寻找链表中点
        ListNode *slow = head, *fast = head, *prev = nullptr;
        while(fast){
            slow = slow -> next;
            if(fast -> next) fast = (fast -> next) -> next;
            else fast = fast -> next;
        }
        // 翻转链表右半部分
        while(slow){
            ListNode *tmp = slow -> next;
            slow -> next = prev;
            prev = slow;
            slow = tmp;
        }
        // check
        while(prev && head){
            if(prev -> val != head -> val) return false;
            prev = prev -> next;
            head = head -> next;
        }
        return true;
    }
};

141 环形链表

标签：链表，环，双指针（快慢指针）
采用快慢指针法，一个走两步，一个走一步，如果两个指针相遇则有环；否则没有
代码：

time: 83.59%, memory: 19.96%
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        // border
        if(!head) return false;
        if(!(head -> next)) return false;
        ListNode *slow = head -> next, *fast = (head -> next) -> next;
        while(fast && (slow != fast)){
            slow = slow -> next;
            fast = fast -> next ? (fast -> next) -> next : fast -> next;
        }
        if(!fast) return false;
        else return true; 
    }
};