LeetCode - 链表中的使用指针的技巧

思路

使用一个指针(java引用)表示当前遍历的链表中的present节点,移动节点的的操作为 p = p.next

注意在链表的拼接操作中，由于链表维护的特性，在拼接了一个节点后，该操作其实是将以该节点为起点的整个链表拼接了过来，在多数情况下可以不对此做额外处理，但有时候需要对尾部节点进行显式地进行 node.next = null操作以防止一些错误出现。（即有时候需要额外处理node.next 属性）

多数情况下(基本上是缺省操作了)，可以使用哨兵节点来简化对于边界情况的处理。

合并两个有序链表

Leetcode21

略

合并K个有序链表

LeetCode23

使用PriorityQueue存放每一个链表的头结点。
利用PriorityQueue的特性，每次poll的时候得到minNode，将该node拼接到新链表中去。
若minNode.next不为空，则将minNode.next加入到PriorityQueue中。重复以上步骤，直到PriorityQueue为空。

分解链表

LeetCode86

合并的逆操作。思路是维护两个List，依具体条件将所有node再分配到两个新list后，再对list合并获取最终结果。

在这种链表合并的过程中，需要特别注意链表节点顺序以及链表是否有回环的问题。为了避免后续合并后的链表出现回环，可以在每次合并连接完成后，将当前节点的下一节点缓存起来，然后将当前节点的next指针显式置为null。不过在此例中，我们可以通过逻辑判断得出，只需要确保最后一个节点的next值为null，就可以保证链表没有回环。

单链表中获取倒数第k个节点

LeetCode19

经典的双指针操作。

一种直接的解法是走 length - k + 1 步即可，但是linkedList一般不维护length，所以为了获取length我们就要先进行一次遍历，那么最终解决这个问题就需要进行两次遍历

使用双指针技巧可以简化为仅进行一次遍历，即先让 p1走k次，然后初始化p2 为head
然后两者同时移动，直到p1指向了末尾的null时，p2也就指向了倒数第k个节点。

（虽然在时间复杂度中，我们可以忽略掉常数项的2，使得两种解法的时间复杂度相同，但是函数的具体实现和算法的运行效率是有区别的。因此，在实际应用中，使用双指针解法会更优，可以获得更快的运行速度和更高的效率。）

获取链表中点

LeetCode876

经典操作，快慢指针，快指针一次步进2步，当快指针走到尾的时候，slow指向了middle

判断回环,是则找到起点

判断的操作也是快慢指针，逻辑完全不变，只是循环步进后多一个判断，slow == fast，若相等则说明有回环。

找起点： slow == fast 时，将任意指针指回head，然后双指针同步步进1个单位，第二次slow == fast时，双指针指向的节点就是回环的起点。

为什么这个方法有效呢？假设链表头到环的起点的距离为a，环的起点到快慢指针相遇点的距离为b，快慢指针相遇点(再次前进)到环的起点的距离为c。当快慢指针相遇时，慢指针走了a+b的距离，快指针走了2(a+b)的距离，且快指针比慢指针多走了一圈，即2(a+b)=a+b+c+b。整理得到a=c。因此，让快指针重新指向链表头部，并与慢指针一起每次移动一步，它们最终相遇的点就是环的起点。

判断两个单链表是否相交，是则找到交点

LeetCode160

一种直接的做法是将一个链表的node存入set，然后不断用另一个list的node进行比对，直至找到第一个重复的node

这套题也可以用双指针的做法优化来 避免使用额外的空间。

trick就是，合并两个链表，一个list1 接到 list2 后面， 一个list1 接到list2 前面。
(具体的代码上可以不做合拼，而是遍历到null后，把指针执行另一个list)
在两个新list上从头开始步进，若有交点，则一定会出现 p1 == p2的情况，若没有交点，也可以涵盖 p1==p2==null的情况