leetcode习题分类汇总-LinkedList篇

Linked List Cycle-原地判断链表是否有圆圈

思路:fast-slow指针,只要存在cycle,fast最终会赶上slow;




### Remove Duplicates from Sorted List-去除有序链表中的重复值



思路:前后两个指针遍历判断即可,时间N




### Remove Duplicates from Sorted List II-把>1次出现的元素都去掉

思路:还是维护fakehead,pre,cur,判断是否有重复,遍历,迭代or递归。





### Merge Two Sorted Lists-归并两个有序链表

思路:链表的归并排序中的merge操作,逻辑清晰




### Swap Nodes in Pairs-每两个交换链表相邻节点,常量空间

思路: 常量空间所以不能用递归,设置一个fakehead,while循环即可,这种题目容易出错,画图比较好。




### Reverse Linked List -翻转单链表,递归or迭代

思路:所谓翻转,其实就是把下一个数不断的转移到上一个数之前,比如1234,21 34,321 4,4321完成,画张图就一目了然。

Linked List Cycle II-判断链表是否有循环,如果有返回循环开始的地方

思路:图网上一堆,所以说…链表的问题首先还是要画图

第一次相遇时slow走过的距离:a+b,fast走过的距离:a+b+c+b。

因为fast的速度是slow的两倍,所以fast走的距离是slow的两倍,有 2(a+b) = a+b+c+b,可以得到a=c(这个结论很重要!)。

我们发现L=b+c=a+b,也就是说,从一开始到二者第一次相遇,循环的次数就等于环的长度。

2. 我们已经得到了结论a=c,那么让两个指针分别从X和Z开始走,每次走一步,那么正好会在Y相遇!也就是环的第一个节点。



扩展问题:

1. 环的长度是多少?

2. 如何找到环中第一个节点(即Linked List Cycle II)?

3. 如何将有环的链表变成单链表(解除环)?

4. 如何判断两个单链表是否有交点?如何找到第一个相交的节点?




### Intersection of Two Linked Lists- 判断两个链表是否有交叉,并返回交叉节点

思路:先计算 AB 的长度,然后把两个链表切割到一样的长度开始判断,时间N空间1;




### Convert Sorted List to Binary Search Tree-把链表转换为BST

思路:BST左》中》右,关键在于找到中间节点,先计算长度/快慢指针,然后DFS遍历,按照左中右的顺序,自底向上构造二叉树,当然也可以自上而下…




### Partition List-切分链表,把<x的节点放在左边,其他放在右边

思路:(1)依然是双指针,画图,找到第一个>=x的节点记录好,然后把左边所有<x的节点放在它左边。

(2)创建两个dummy1,dummy2节点,遍历一遍,cur1遍历dummy1存放<x的节点,cur2遍历dummy2存放>x的节点,最后两个节点连在一起即可,注意cur2.next要设置为null,否则就成为head循环了



### Remove Nth Node From End of List-去除链表的倒数第N个元素,尝试一次遍历搞定

思路:快慢指针,快指针先行N步骤,之后前后保持N的距离,fast到末尾后,slow skip掉下一个节点即可。


Insertion Sort List-链表的插入排序

思路:设置一个fakehead,然后和插入排序一样,设置一个pre节点,cur节点,遍历,每次在pre-cur之前寻找合适位置插入,保持cur左边有序。时间还是N2.



### Reverse Linked List II-根据m,n值翻转链表,1<=m<=n<=length 一次遍历

思路:这样的题目关键是不要怕麻烦,一定要画多几个链表图,一步一步演算,这样思路就很清晰了。设置一个fakehead(或者不设置之后进行判断,设置两个m,n节点,维护一个premNode,中间保持m-n距离遍历到指定位置,然后把m不断插入到n后直到m,n相遇。




### Remove Linked List Elements-去掉链表中国所有的指定值

思路:设置fakehead节点, pre,cur指针遍历就行




### Reverse Nodes in k-Group-以k为组翻转链表

思路:循环的翻转链表,只需要维护一个count值就可以,本质还是翻转。多加练习




### Copy List with Random Pointer-复制有任意指针的链表

思路:插入拷贝节点,复制random指针,分解至两个独立列表

Sort List —— 常量空间下 O(nlogn)时间排序链表

思路:链表的归并排序,一开始想到快排,后来发现递归调用不满足要求,所以归并可以采取迭代的方式mergesort以及merge,当然递归的代码更加容易理解一点,有点理解为啥不要在面试的时候回答链表的题目了,太容易出错了


Rotate List-翻转链表k个体位

思路:还是利用fast-slow指针,fakehead等常见手法,写烂了…只是主要要用k%i判断k是否大于链表的长度i;




### Add Two Numbers-两个链表每个节点分别表示一个数字,求数字相加的第三个链表,可以进位

思路: carry表示进位,p1,p2,p3遍历,考虑链表长度不同的状况




### Merge k Sorted Lists-归并k个有序链表

思路:

(1)
这道题目在分布式系统中非常常见,来自不同client的sorted list要在central server上面merge起来。
这个题目一般有两种做法,下面一一介绍并且分析复杂度。 第一种做法比较容易想到,就是有点类似于MergeSort的思路,
就是分治法,不了解MergeSort的朋友,请参见归并排序-维基百科,是一个比较经典的O(nlogn)的排序算法,
还是比较重要的。思路是先分成两个子任务,然后递归求子任务,最后回溯回来。这个题目也是这样,先把k个list分成两半,然后继续划分,知道剩下两个list就合并起来我们来分析一下上述算法的时间复杂度。假设总共有k个list,每个list的最大长度是n,那么运行时间满足递推式T(k) = 2T(k/2)+O(nk)。根据主定理,可以算出算法的总复杂度是O(nklogk) 。如果不了解主定理的朋友,可以参见主定理-维基百科。空间复杂度的话是递归栈的大小O(logk)。

(2)接下来我们来看第二种方法。这种方法用到了堆的数据结构,思路比较难想到,但是其实原理比较简单。维护一个大小为k的堆,

 每次取堆顶的最小元素放到结果中,然后读取该元素的下一个元素放入堆中,重新维护好。因为每个链表是有序的,每次又是去当前k
个元素中最小的,所以当所有链表都读完时结束,这个时候所有元素按从小到大放在结果链表中。
这个算法每个元素要读取一次,即是kn次,然后每次读取元素要把新元素插入堆中要logk的复杂度,
所以总时间复杂度是O(nklogk)。空间复杂度是堆的大小,即为O(k)。
感觉就是链表的堆排序实现嘛。自己感觉还是挺少见的…







### Reorder List-Given a singly linked list L: _L_0→_L_1→…→L__n-1→_L_n,
reorder it to: _L_0→L__n→_L_1→L__n-1→_L_2→L__n-2→…






思路:
(1)Break list in the middle to two lists (use fast & slow pointers)
(2)Reverse the order of the second list
(3)Merge two list back together
其实很多题目可以归约为其他若干个基础问题的综合,比如这题的fast-slow指针,链表的翻转,链表的插入。

总结:链表的题目不多,难度也不大,但是容易出错,做这些题的要点就两个:*1.画图。2.掌握基本的fast-slow指针,翻转,归并等技巧灵活运用。