Linked List (Java) - ShuweiLeung/Thinking GitHub Wiki

该页笔记始于"2018.5.27"，结于“2018.6.1”，使用Java语言

关于链表问题中"pre指针的初始化"

链表处理的过程中常涉及到"cur和pre指针的互操作"，当cur为头结点时，它没有前一个结点，此时我们常把pre设为null。当cur不为头结点，pre一般情况下就是当前cur的前一个结点。

链表中的"快慢指针"

从Linked List类别的问题中，我们可以发现“快慢指针”在该tag中应用非常广泛。从目前做过的题目当中，它可以：1.判断链表是否有环 2.求得链表长度的中点

1.（237:Easy）（非常经典题）Delete Node in a Linked List

该题主要对链表存储的考察。在一般情况下，要删除链表的一个节点，需要知道当前节点的前驱节点。该题没有给出前驱节点，所以就需要将当前节点的后继节点的值复制到当前节点，然后删除后继节点即可。

2.（206:Easy）（非常经典题）Reverse Linked List

iterative 解法：总结就是得到下一个节点，更改当前节点指向，将指针往下移动，直到过完整个linkedlist.
recursive 解法：总结是传给helper method两个节点，cur和pre（最开始是head和null), 先用n1存当前节点的next，然后把当前节点的next指向pre，然后一直recursively call help method直到过完整个linkedlist.
具体思路参看代码实现。

参考链接：迭代和递归解法

该题用dfs不知道为什么会内存溢出，下次复习时与同学请教讨论

3.（21:Easy）（经典题）Merge Two Sorted Lists

设立两个指针cur1和cur2分别指向l1和l2，然后设立pre指向合并后的链表，比较cur1和cur2的结点值，将较小的节点插入新链表，并将pre指针后移。

4.（83:Easy）Remove Duplicates from Sorted List

设立一个pre指针，设立一个cur指针指向pre之后的结点，当pre的结点值和cur的结点值相同的时候，cur后移直到第一个与pre结点值不相同的结点，然后更新pre指针位置和cur指针，重复上述操作。

5.（141:Easy）（非常非常经典题）Linked List Cycle

首先需要注意：链表中的环不一定是首尾相连，也可能是链表中间某个结点和尾结点相连接。
正如Array类中的一题相似，我们需要设立两个快慢指针，若有环，这两个指针一定会相遇。

6.（203:Easy）Remove Linked List Elements

只需要遍历链表寻找节点值与给定值相等的结点，然后将其删去就可以了

7.（234:Easy）（非常非常经典题）Palindrome Linked List

使用快慢指针和链表倒置进行判断。
This can be solved by reversing the 2nd half and compare the two halves. Let's start with an example [1, 1, 2, 1].
In the beginning, set two pointers fast and slow starting at the head.

1 -> 1 -> 2 -> 1 -> null

(1) Move: fast pointer goes to the end, and slow goes to the middle.

1 -> 1 -> 2 -> 1 -> _null_ 
          s          f

(2) Reverse: the right half is reversed, and slow pointer becomes the 2nd head.

1 -> 1    null <- 2 <- 1      
h                      s

(3) Compare: run the two pointers head and slow together and compare.

1 -> 1    null <- 2 <- 1             
     h            s

8.（160:Easy）（非常非常经典题）Intersection of Two Linked Lists

一开始尝试使用set集合存储listA的链表结点，之后再遍历listB的结点，并判断listB当前结点是否在set集合中，但该方法超时。
其实，该题的关键是，使listA和listB的遍历起点是在同一起跑线上的，在这里我们使用一个小的技巧，当listA遍历到结尾后，跳转到listB的起点继续遍历。同理，当listB遍历到结尾后，跳转到listA的起点继续遍历。示意图如下：

listA: A1-A2-A3-A4-C1-C2-C3
listB: B1-B2-C1-C2-C3
我们将listA与listB连起来，那么遍历路径将变为
A: A1-A2-A3-A4-C1-C2-C3-B1-B2-C1-C2-C3
	 	        *     ^
B: B1-B2-C1-C2-C3-A1-A2-A3-A4-C1-C2-C3
		        *     ^

我们可以发现经过两个链表头尾的连接，从*号位置开始两个链表指针从相同起点开始进行遍历，在^处发现相交点。具体实现请参看代码。
参考链接：中文思路视频讲解

9.（817:Medium）Linked List Components

该题不知道想考察什么，只要是连续的结点值都在题目给的list G中，那么就算做一个component，单独一个结点如果出现在G中也算一个component

10.（725:Medium）（经典题）Split Linked List in Parts

该题关键点是：1. 当k大于链表长度时，每个部分长度最大为1，后边的分段均为null 2.当k小于链表长度时，可能分段长度有大有小，但最多不能相差1个单位。对于长度稍长的分段个数，我们可以利用地板除法的性质来求出来，代码如下：

int avgLen = len / k;  //每个片段的最小长度，最大长度只能比最小长度多1
int moreThan1 = len - avgLen * k;  //比平均长度多1的分段个数（利用地板除法求得该片段长度比最短长度多1的个数）

根据上面两种情况分别处理即可，具体实现细节参见代码。

11.（445:Medium）（非常非常经典题）Add Two Numbers II

该题与Leetcode 第2题相似，当然也可以用StringBuilder，然后结合字符串加法的算法来进行求解（同Leetcode 第2题），但实现比较复杂，可能会出错。
该题的参考答案是使用Stack，将链表压入栈中，因为题目中链表是由高位指向低位的，所以当弹出时就是先弹的低位，然后求和，用取余操作来获得当前结点的值。具体实现思路参看代码实现，有注释。

12.（328:Medium）（非常经典题）Odd Even Linked List

核心思想是，用两个指针odd1、even1分别指向已经处理好的奇数链和偶数链结尾，然后用两个指针odd2、even2指向下一对待处理奇数结点和偶数结点，将当前待处理的odd2和even2分别加入奇数链和偶数链末尾，然后将四个指针均后移，进行下一对奇数结点和偶数结点的处理。具体思路可以参看代码实现。
其次，题目中说的奇数偶数是指次序上的奇偶，而不是结点值的奇偶。

13.（24:Medium）（经典题）Swap Nodes in Pairs

该题其实和第12题（328）相似，但难度并没有第12题（328）大，也是设立两个指针pair1和pair2分别指向奇偶对的第一元素和第二个元素，交换两结点位置后，向后移动即可。此外需要设立一个pre指针指向之前已交换结点位置的链表结尾，用于连接新旧链表。

14.（109:Medium）（非常非常经典题）Convert Sorted List to Binary Search Tree

该题与Leetcode 108题.Convert Sorted Array to Binary Search Tree非常相似，所以一开始感觉没法在不知道链表长度的情况下求得当前链表长度的中点，所以先将其遍历一遍，把结点值存入ArrayList，然后再按照Leetcode 108题的思路从上到下建树，但该思路超时。
看了discuss答案后，发现该题其实是用快慢指针来寻找当前链表片段的中点，当快指针到达当前链表片段的结尾时，慢指针指向的就是中点结点，之后再递归由上到下（而不是由下到上）建立BST即可。
注意：我们可以将递归函数的返回值设为TreeNode，从而不用在向下递归搜索时传入方向参数。

15.（147:Medium）Insertion Sort List

该题就是一个插入排序的简单变种，从已排序链表的开始重头搜索，找到合适位置插入即可。

该题除了自己实现的方法思路，好像还有更简单的方法

16.（19:Medium）（非常经典题）Remove Nth Node From End of List

该题如果要一次遍历，必然要使用快慢指针，那么快指针可以优先得到链表长度，如果待删除结点在慢指针之后，直接后移慢指针即可；如果在慢指针之前，则需要重置慢指针到初始位置，重新遍历链表。（beat 27%）

该题更高效的方法也是快慢指针，但好像不用回调慢指针位置，下次复习时参看discuss学习

17.（86:Medium）（经典题）Partition List

该题其实与第13题（24）思路一样，设置两个指针lessHead、egHead分别指向“比给定值x小”的链表头结点与“大于等于x”的链表头结点，设置另外两个指针lessTail、egTail分别指向这两个链表的尾结点用于构造链表，再设置另外一个指针cur指向未处理的结点。
注意，需要考虑边界情况：1. 可能链表中所有节点的值都小于x。 2.也可能链表中所有节点的值都大于等于x

18.（92:Medium）（非常经典题）Reverse Linked List II

该题是第3题（21）的扩展，其实链表反转的步骤比较简单。关键是，被反转的链表只是整个链表的一部分，因此，我们可以将待处理的m->n链表拿出来反转后再插入原链表即可，这样的话，我们就需要保存第m-1个结点和第n+1个结点，以便后续将反转后的链表重新插入进去。
注意，我们需要考虑两个边界情况：1. m=n，此时直接返回原来的head头结点即可 2. m=1，此时，处理后的链表头结点发生变化，新的头结点应该是原来的第n个结点

19.（142:Medium）（非常非常经典题）Linked List Cycle II

该题其实是非常非常经典的快慢指针应用题目。该题也是第5题（141）的进一步扩展。其实该题已经在Array类题目中出现，具体可以参见Leetcode 第287题，同时也可以参看该题的笔记。

我们还是拿Leetcode 第287题的图来讲解思路。在水平轴上快慢指针都走过了s的长度，假设慢指针在环上只走了m的距离，此时即被快指针追及相遇。又因为快指针走过的距离应该是慢指针距离的2倍，假设圆环的周长为r，这样我们可以写出关系式：2(s + m) = s + m + r。化简该表达式，我们可以得出r = s + m，因为现在快指针和慢指针已经相对环的起始点走过了m的距离，有r - m = s，所以若将快指针重置到head结点，以步速为1的速度向前移动，那么快慢指针会同时在环的起始点O相遇，从而得出答案。

20.（148:Medium）（非常非常经典题）Sort List

该题提示时间复杂度为O(nlogn)，所以肯定需要使用分治思想来求解。那么对于链表这种不知道长度的数据结构而言，要想分治，在获得长度的同时找到中间结点，那就不得不适用快慢指针了。根据快慢指针我们找到当前链表的中点，并向下递归，然后再merge即可。因为题目要求使用常数空间复杂度，所以我们不能新建与链表长度成正比的新变量。我们可以分析出，对于两条已排序的链表，在merge的过程中，我们只需要设立额外的两个与归并链表长度无关的指针newhead和newtail即可，然后同时扫描待归并的两个链表，将较小的头结点截下插入newtail之后即可，使用常数空间复杂度。
那么在merge-sort过程中，我们需要注意几点：1. 我们并不是以慢指针slow为分界点进行二分的，因为当链表长度为2时，slow总是指向第二个结点，从而会出现向下无限递归的情况，因此，我们应该以slow的前一个结点prev作为分界点。 2. 在向下二分递归的过程中，我们应该确保向下传递的两条链表的尾结点的next指针为null，这会方便我们在merge两个已排序的链表时，不用关注他们的尾结点是否与额外的第三个链表有联系。 3.在进行merge时，我们可以自己自定义一个头结点，如newhead = new LinkedList(0)，这里的newhead结点是有值的，但却方便了其他结点的插入，在插入时不用判断是否newhead为null，这样的话，最后在向上层返回时，只需返回归并后真正的头结点newhead.next即可。

21.（82:Medium）（经典题）Remove Duplicates from Sorted List II

该题首先要找到重复的结点，然后根据重复结点来去重。这里有一个小技巧，即在第20题（148）中提到的注意事项第3条，因为题目中给的head也可能是重复的，所以最后返回的newhead结点与head不一定相同，为了简化代码操作，可以自己建一个newhead = LinkedList(0)，然后将distinct结点插入尾部即可，最后返回newhead.next。

22.（143:Medium）（非常经典题）Reorder List

其实仔细观察题目的说明，我们会发现，它是将reverse后的链表进行了重排序，该题是一道综合题，将之前的知识点全部都糅合在一起。具体来讲，解决这道题分三步走：

通过快慢指针找到链表的中点，我们这里把最后循环跳出的slow指针位置当作中点
reverse 后半部分的链表，也包括slow结点
根据前半部分和reverse后的后半部分链表，我们进行reorder，先取第一部分的第一个结点，再去第二部分的第二个结点，交替选取即可。

23.（61:Medium）Rotate List

该题其实比较简单，求出整个list的长度后，更新k的值，即k = k % len，然后从倒数第k个结点前截断，将截断的部分连接到原来链表的开头即可。

24.（25:Hard）Reverse Nodes in k-Group

该题其实很简单，就是一个rever linked list的变种，只不过该题要求是每k个结点进行一次reverse而已，当剩余结点的个数少于k时，我们不进行reverse。具体实现思路看代码，beat 100%。

25.（23:Hard）（非常经典题）Merge k Sorted Lists

该题我的做法是，每次遍历所有链表，从中找出最小的结点值的下标索引存入ArrayList(如果单独处理的话会超时)，然后插入待返回链表的末尾，然后将指向这些最小结点链表的指针后移一位，继续遍历。但该方法效率比较低，只beat 8%。
该题第二种方法是借用Priority Queue的自动排序机制，每次取一个堆顶元素插入到待返回链表中，效率更高，beat 58%。

26.（876:Easy）（经典题）Middle of the Linked List

快慢指针在链表当中的典型应用