花2天把Leetcode上Linked lists的题目刷完了，下面是一些我觉得比较有倾诉欲望的题。

237. Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

这道题我的第一反应是，it's impossible！只给了这个node，鬼知道它前面那个node是啥呀，这不是怎么都找不到的么。后来看了答案觉得真是骨骼清奇，它采取的并不是寻常的找到前一个node，改变pointer这样的方式，而是很tricky地，先将这个node的值改成下一个node的值，然后删掉下一个node。不过话说回来，这道题我觉得并不是很合理，严格来说这不算删掉了这个node，它删掉的是下一个node，不太严谨。不过当做一种思路的扩充吧。

class Solution {
public:
    void deleteNode(ListNode* node) 
    {
        node->val = node->next->val;
        ListNode* next = node->next->next;
        delete node->next;
        node->next = next;
    }
};

206. Reverse Linked List

Reverse a singly linked list.
Hint:A linked list can be reversed either iteratively or recursively. Could you implement both?

这题我觉得很好，用两种方式来翻转链表，越基础越是需要掌握。

Iteratively的做法，如果不借助其他pointer的帮助，我们只能每次都从头找到尾，太笨了。如果设置一个prev pointer，那么对cur node来说，前后关节打通了，实际上成为了一个双向链表，操纵一下pointer就可以实现翻转了，不是什么难事。这里的思想方法其实就是把单向链表转化为双向链表来做。

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* prev = nullptr;
        ListNode* next;
        while (head)
        {
            next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

Recursively的做法，比前者稍微难一点。这个方法我并没有自己想出来，我的思路是：要翻转这个链表，肯定要先翻转cur->next这个链表……这么下去到最后一个链表返回的就是最后一个node。我们需要实现：return node->next = head，但是最后我们需要返回的结果却是最后一个node，这就要求我们能return两个值，无法实现。所以我就卡住了。

这种思路其实也挺正常的，但是当思路不对的时候，应该再想想有没有其它思路——这点也许是我欠缺的。答案中，我们return node就是最后一个node，那么难点就在于如何将head和后面一个已经反转的链表联系起来。其实稍微想一想就得出，head->next->next = head就可以实现目标了。

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        if (!head || !head->next) return head;
        ListNode* last = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return last;
    }
};

其实再仔细一想，作为一个recursion，写的时候其实可以把结构都先描画出来，像列提纲一样，就是把recurse()和return x;写好在那边，那目标就很明确，我们在利用recursion解决什么subproblem，我们最后要返回的是什么。我们最后要返回的是什么，这点在recursion中至关重要，却也最容易迷失。recursion的问题其实就是假设这个recursion works，subproblem已经解决了，对于解决这个整个问题有什么用处，recursion就像一个api一样，是让我们去调用的，最终在于返回一个结果。当我们将最后我们要返回什么搞清楚，很多时候问题就清楚了。

141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?

这道题利用了Floyd's hare and tortoise algorithm来找到cycle。以下的证明供我自己容易理解、记住而得：

• 算法：已知一个链表存在循环，用两个指针，一快一慢，快的速度是慢的两倍，从头开始iterate这个链表，那么它们一定会在某一个node相遇。

• 证明：最intuitive的思想：当慢指针刚刚进入循环，快指针已经进入循环中的某一个节点了，因为快慢指针相对速度差一个节点，慢指针进步一格，快指针进步两格，这相当于说慢指针不动，快指针进步一格，这样快指针肯定能追上慢指针，它们一定会相遇。

• 算法：将快指针放到链表开头，慢指针依旧在两者相遇处，每次两格指针同时前进一格，第二次它们相遇的节点，就是循环的开始。

• 证明：令循环长度为n，进入循环前的长度为x，循环开始到相遇地距离为y，相遇地到循环开始距离为z。到相遇时，慢指针走过的距离是d=x+y，快指针走过的距离是D=x+y+kn。假如k>1，那么说明快指针

与#142题相结合，以下是检测有无cycle以及返回cycle开始的节点的代码：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        ListNode* copy = head, *slow = head, *fast = head;
        while (fast && fast->next && fast->next->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (fast == slow) break;
        }
        if (!fast || !fast->next || !fast->next->next) return nullptr;
        slow = head;
        while (fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

时间复杂度为O(N+K)，其中N是循环起点之前的node数，K是循环node数。因为在循环中转了一圈之后，快指针肯定能追上慢指针了。空间复杂度为O(1)。

160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

这道题我有几种思路：
1、延续前面讨论过的龟兔赛跑算法，完全可以找出这个node，也就是循环开始的这个node。当然，用这种方法要先构造出一个环路，最后把结构还原就行了。
2、可以通过判断最后一个节点是否一样来判断两个链表有无交集。如果有交集，可以通过计算长度来判断交集点。因为从交集开始到结尾，两个链表的长度一样，那么两个链表长度之差，也就是两个链表从开头到交集长度的差。所以我采取的方法是，将长度都算出来，将较长的那个链表的指针往前移difference位，然后两个指针一起出发，相交点即为所求节点：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        if (!headA || !headB) return nullptr;
        ListNode *copy_A = headA, *copy_B = headB;
        int len_A = 0, len_B = 0;
        while (headA->next) { headA = headA->next; ++len_A; }
        while (headB->next) { headB = headB->next; ++len_B; }
        if (headA != headB) return nullptr;
        int dif = abs(len_A - len_B);
        if (len_A > len_B) 
        {
            while (dif--) copy_A = copy_A->next;
        }
        else 
        {
            while (dif--) copy_B = copy_B->next;
        }
        while (copy_A->next)
        {
            if (copy_A == copy_B) return copy_A;
            copy_A = copy_A->next;
            copy_B = copy_B->next;
        }
        return copy_A;
    }
};

这个代码很长很难看，后来去discussion区看了一下，有更精简的表述方法：原解答网址。Code摘抄如下：

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
{
    ListNode *p1 = headA;
    ListNode *p2 = headB;
        
    if (p1 == NULL || p2 == NULL) return NULL;

    while (p1 != NULL && p2 != NULL && p1 != p2) {
        p1 = p1->next;
        p2 = p2->next;

        // 如果从链表开头到交集的长度一致，那么这一行就返回所找到交集节点
        // 当两者没有交集，也用了这一行
        if (p1 == p2) return p1; 
    
        // 如果短链表提前走完了，将指针置于长链表开端
        // 等到长链表的指针也走完了，将指针置于短链表开端
        // 而这时候，之前放置的长链表指针已经多走了difference步了
        if (p1 == NULL) p1 = headB; 
        if (p2 == NULL) p2 = headA;
    }
        
    return p1;
}

138. Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

这道题的code很简单不贴了，思维过程值得回顾一下。

分析题意：

• deep copy：
  • 说明需要新建node，而不只是对pointer的操纵
  • 说明原来的node不能变动
• next pointer没什么花头，关键点在于怎么去对应这个random pointer。由于原来的random pointer指的是原来的node list中的node，现在的random pointer指的是新node list中的node，需要一种方法将原来的node和新的node一一对应

我一开始做的时候，想的是，将原来node的next pointer指到对应的现在node，现在node的random pointer指到原来node。这样一来，上下互通。但是这个问题是，一旦现在node的random pointer被修改了以后，就无法复原原来的pointer。所以这种方法不对。

看了答案，是将新node插入进两个老node里。另外值得注意的是，写code的时候对于nullptr这种情况要分外注意，有两次提交失误都是因为没有注意nullptr。

234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

这道题是检验前面几题有没有白做了的范例。前面几题用到的知识中最重要的亮点——fast/slow pointer； use a prev pointer in singly linked list。将这两点与这题相结合，得出方法：用slow/fast pointer法+reverse list法将前半个list翻转，然后从中间向两边对照数字。其中注意奇偶不同和nullptr的检验。

19. Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.

巨喜欢这道题，因为它很灵活地考察了fast slow pointer。看到这道题的时候，我知道找到这个node之后，操纵pointer是很轻松的事情。主要是怎么来找到这个node。如果N是开头到这个node的距离，那么一遍就能找到并且删掉。现在N是node到结尾的距离，我第一反应肯定要用到fast slow pointer，但是两倍的fast slow pointer很难应用啊。然后想了几种很复杂的方法，觉得不太符合题目“in one pass”的要求。然后也有点赶时间，就看答案了。

我来试图模拟得到这个答案的思维过程：如果node到结尾的距离是N，整个list长L，那么从开头到这个node的距离是L-N。也就是让pointer走L-N距离就可以找到这个node了。让pointer走L-N距离有两种方法，一种是从开头走到这个node，一种是从开头+N走到最后。所以我们只要先将fast pointer往前挪N，然后跟slow pointer一起每次一格走到最后，slow pointer所得到的就是要被删的node。

这道题属于灵活应用的“微创新”题，真的很喜欢，希望下次自己能想出来。砰砰砰。

23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

这道题其实挺有意思的。从merge two lists到merge k lists，第一个想到的是divide and conquer，把问题分解成merge two lists就好了。这样的解法空间复杂度是O（logk），k是lists中list的数量，时间复杂度是O（nlogk），n是总共的node数，因为每一层merge的时候复杂度都是O（n），一共有logk层。另外还有一种解法是用priority queue，这个利用了priority queue的自带sorting性质，每次我们将list的开头push到这个queue里，queue里最多有k个node。code挺简单的就不贴了。关于priority queue的底层implementation抽空再复习一下。

<Reorder list>

有不少题是关于调换linked list中元素的位置的，甚至是将list转换为tree。这种题啊换汤不换药。快慢指针、设置prev pointer，可以说是套路至极了。

总结：
1、多想想fast/slow pointer，其中包括fast pointer比slow pointer跑的快一倍的（用于找中间数，找到cycle等），也包括fast比slow跑的不是两倍的。这两个指针可以用来解决很多在单向链表中关于距离的问题。
2、对于singly linked lists, 多想想设置一个prev pointer使之成为本质上的doubly linked lists
3、小心犯错误的code detail：
1）在操纵pointer的时候，小心前面的pointer变化影响到后面
2）考虑nullptr的情况
3）对一个node的前后node要多检查