花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要多检查