LeetCode linked-list 问题总结

2017-03-23

LeetCode linked-list 问题的总结

Easy

141. Linked List Cycle 使用 fast 和 slow 指针,fast 每次走两步,slow 每次走一步,如果它们相遇,说明链表有环;否则链表无环。

142. Linked List Cycle II 先用 No. 141 的方法是否存在环。如果存在的话,求出环的长度 len,然后依然使用双指针。一开始两指针 p 和 q 都指向头结点,先让指针 p 从链表头走 len 步,然后 p 和 q 同时前进,当它们相遇时,相遇结点就是环的入口。

237. Delete Node in a Linked List 因为不用考虑要删除的结点处于链表尾部,所以我们可以交换当前结点和下一节点的值,然后删除下一节点就行了。

83. Remove Duplicates from Sorted List Add to List 考虑到链表已经有序,用双指针就可以解决。只保留每一类元素的一个,并跳过其他冗余元素。改变指针指向就可以删除冗余值了。

160. Intersection of Two Linked Lists 如果两个链表交叉,那么从交叉点开始,这两个链表就合成一个链表了。可以用双指针解决,首先遍历两个链表得到它们的长度,长链表为 m,短链表为 n。那么可以先在长链表上走 m-n 步,然后同时在两个链表开始遍历,当这两个指针第一次相等时,这个节点就是链表的交叉处。如果这两个链表始终不相等,说明链表不交叉。

203. Remove Linked List Elements 链表的删除操作。要注意的是头结点有可能被删除,处理这种情况的一个方法是使用一个哨兵结点,使得它指向头结点,然后我们从哨兵结点开始操作。

206. Reverse Linked List 基本操作,有迭代和递归两种方法。

234. Palindrome Linked List 考虑到只能使用常数空间,那么可能先对链表前半部分或者后半部分反转,将链表分为两半的操作可以使用 slow 和 fast 指针。反转完成之后就可以开始判断了。

21. Merge Two Sorted Lists 因为不允许创建新的结点,其实就是将一个有序链表的元素插入到另一个有序链表。

Medium

61. Rotate List 注意 k 可能大于链表长度,首先应该遍历链表求得长度 len,然后让 k 对 leng 取模,即 k = k % len。如果 k 为 0 就直接返回,否则就将链表尾 k 个结点移到链表头。

147. Insertion Sort List 像插入排序那样使用两层循环就行了。依然使用哨兵结点处理可能会头结点进行更改的情况。

138. Copy List with Random Pointer 解法参考剑指 offer 的面试题 26。大致思路先在原链表的基础上复制结点,然后处理 random 指针,最后将新链表和原链表分离出来。

109. Convert Sorted List to Binary Search Tree 如果使用 O(n) 空间的话,一个方法是将链表元素放入一个向量 nums 中,然后用向量的中间元素 nums[mid] 做根结点,那么 mid 左边的元素就是左子树,mid 右边的元素就是右子树,递归处理就好了。当然如果不用空间的话,那么用 fast 和 slow 指针一样可以找到链表的中间元素做根节点,剩下的也是递归处理。

92. Reverse Linked List II 相当于将链表从 m 个节点 到第 n 个节点做反转。所以只需要找出 m 和 n 对应节点位置,那么剩下的工作就和链表反转一样了。为了方便处理,这里仍然可以使用一个哨兵节点。

86. Partition List 可以使用快排的 partition 思想,使用两个指针 p 和 q,p 左边的节点都小于 x,p 到 q 之间的节点(包括 p)都大于或等于 x,q 之前的节点还没有处理。这样扫描一遍链表就可以了。

82. Remove Duplicates from Sorted List II 涉及到对链表节点的删除操作,不过要注意的是可能删除头结点,可以使用哨兵节点或者指针的指针来处理。

445. Add Two Numbers II 如果可以修改链表,那么可以将链表反转再计算,计算完成后,记得将结果反转;如果不可以修改链表,这时需要额外的空间,可以使用栈解决;另一个不修改链表并且不需要额外空间的办法是使用递归。

328. Odd Even Linked List 可以首先将链表分为两个链表,分别包括奇数节点和偶数节点,然后再将两个链表串在一起。

19. Remove Nth Node From End of List 仍然使用双指针的方法,指针 p 在前,指针 q 在后,两个指针相隔 n 个节点;当 p 到达链表尾部为空时,q 的下一个节点就是要删除的节点。

2. Add Two Numbers 因为数字已经反向存储在链表中了,所以我们直接遍历两个链表进行运算就可以了。

24. Swap Nodes in Pairs 链表删除和插入,因为会改变头结点,所以可以使用哨兵节点或者指针的指针。

Hard

25. Reverse Nodes in k-Group 相当于将链表分成许多组,每组分别做反转。

23. Merge k Sorted Lists 每次从 vector 拿出两条链表合并,合并完成后再将新链表放入 vector,重复这个过程直到只剩下一条链表。