之前链表的题确实没做够啊~

141. Linked List Cycle

Analysis

判断链表中是否存在环，很直观的做法就是利用哈希表了，如果访问过的结点又再次被访问了，那么一定存在环。

Code

method 1

直接用 set 容器来构造一个哈希表。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == nullptr) return false;
        ListNode *p = head;
        unordered_set<ListNode*> ht;
        while(p) {
            if(ht.find(p) != ht.end()) return true;
            ht.insert(p);
            p = p->next;
        }
        return false;
    }
};

method 2

有个进阶提示，如何能在常量的空间复杂度解决这个问题。
有了做 202. Happy Number 的经验，这里很自然就会想到用快慢指针来解决这个问题。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == nullptr) return false;
        ListNode *slow = head, *fast = head->next;
        while(fast && slow != fast) {
            slow = slow->next;
            fast = fast->next ? fast->next->next : fast->next;
        }
        return fast != nullptr;
    }
};

注意，如果不存在循环链表，并且 fast 指向的是倒数第二个结点时，直接跳 2 个结点会出错，因为那个结点是不存在的，所以需要判断一下。当然，也可以在开始的时候将快慢指针设置一样。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == nullptr) return false;
        ListNode *slow = head, *fast = head;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow) return true;
        }
        return false;
    }
};

21. Merge Two Sorted Lists

这个题是做的题，参考：Leetcode_14 天算法入门_day10。
嗯，代码就不贴了，再写一下就行了。

203. Remove Linked List Elements

Analysis

感觉这个题比上个题容易，只要删除链表中值为 val 的结点就可以了。先找到结点位置，然后在删除。

Code

method 1

借助哑结点来完成，比较简单。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *L = new ListNode;
        ListNode *p = L, *cur;
        p->next = head;
        while(p) {
            if(p->next && p->next->val == val) {
                cur = p->next;
                p->next = cur->next;
                delete(cur);
            } else p = p->next;
        }
        p = L;
        L = L->next;
        delete(p);
        return L;
    }
};

method 2

同样，这个题依然可以用递归来做，就是有点难想到啊。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(head == nullptr) return head;
        head->next = removeElements(head->next, val);
        return head->val == val ? head->next : head;
    }
};

Summary

这几个链表题感觉比较简单、常规，不过递归的做法真难想啊。