第 1 关 | 原来链表怎么有用：2.白银挑战——链表高频面试算法题-灵析社区
时光小少年1. 两个链表的第一个公共子节点
这是一道经典的链表问题，剑指 offer 52 ：输出两个链表，找出它们的第一个公共节点。例如下面的两个链表：
两个链表的头结点都是已知的，相交之后成为一个单链表，但是相交的位置未知，并且在相交之前的结点数也是未知的，请设计算法找到两个算法的合并点。
分析：
首先来理解一下，这个题是什么意思。思考一下下面两个图，是否都满足单链表的要求，为什么？
第二个图：
解析：
上面第一个图是满足单链表要求的，因为我们说链表环环相扣，核心是一个结点只能有一个后继，但不代表一个结点只能有一个被指向。第一个图中，c1 被 a2 和 b3 同时指向，这是没关系的。这就好比法律倡导一夫一妻，你只能爱一个人，但是可以多个人爱你。
第二个图就不满足要求，因为 C1 有两个后继 a5 和b4。
理解了题目含义之后，我们继续来看如何解决。
没有思路如何解题？
单链表中的每个节点只能指向唯一的下一个next，但是可以有多个指针指向同一个节点。例如上面的 C1 可以被多个节点同时指向，这种问题该如下下手呢？如果一时想不到该怎么办呢？
告诉你一个屡试不爽的办法，把常用数据结构和常用算法想一遍，看看哪些能解决问题。
常用的数据结构有数组、链表、队、栈、Hash、集合、树、堆。常用的算法思想有查找、排序、双指针、迭代、递归、分治、贪心、回溯和动态规划等等。
首先想到的暴力法，类似于冒泡排序的方式，将第一个链表中的每一个结点一次和第二个链表相互比较，直到出现相等的结点指针时，即为相交结点。虽然建党，但是复杂度高，排除！
再看Hash，先将第一个链表元素全部存到Map里，然后一边遍历第二个链表，一边检测当前元素是否在Hash中，如果两个链表有交点，那就找到了。OK，第二种方法出来了。既然Hash可以，那集合呢？和Hash一样用，也能解决，OK，第三种方法出来了。
队列和栈呢？这里用队列没啥用，但用栈呢？现将两个链表分别压到两个栈里，之后一边同时出栈，一边比较出栈元素是否一致，如果一致则说明存在相交，然后继续找，最晚出栈的那组一致的节点就是要找的位置，于是就有了第四种方法。
这时候可以直接和面试官说，应该可以用HashMap做，另外集合和栈应该也能解决问题。面试官很明显就会问你，怎么解决？
然后你可以继续说HashMap、集合和栈具体应该怎么解决。
假如你想错了，比如你开始说队列能，但后面发现根本解决不了，这时候直接对面试官说“队列不行，我想想其他方法”就可以了，一般对方就不会再细究了。算法面试本身也是一个相互交流的过程，如果有些地方你不清楚，他甚至会提醒你一下，所以不用紧张。
除此上面的方法，还有两种比较巧妙的方法，比较巧妙的方法我们放在第六小节看，这里我们先看两种基本的方式。
1.1. 哈希和集合
先将一个链表元素全部存到Map里，然后一边遍历第二个链表，一边检测Hash中是否存在当前结点，如果有交点，那么一定能检测出来。 对于本题，如果使用集合更适合，而且代码也更简洁。思路和上面的一样，直接看代码：
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> set = new HashSet<>();
while(headA != null){
set.add(headA);
headA = headA.next;
}
while(headB!= null){
if(set.contains(headB)){
return headB;
}
headB=headB.next;
}
return null;
}
# 方法1，使用集合
def getIntersectionNode(self, headA, headB):
s = set()
p, q = headA, headB
while p:
s.add(p)
p = p.next
while q:
if q in s:
return q
q = q.next
return None
由于在 C语言的基础包里面没有定义集合类型，所以这里如果需要用到集合的话需要我们自己先构建一个，或者引入外部资源包，这个更加麻烦，所以我们这里不提供代码。
1.2. 使用栈
这里需要使用两个栈，分别将两个链表的结点入两个栈，然后分别出栈，如果相等就继续出栈，一直找到最晚出栈的那一组。这种方式需要两个O(n)的空间，所以在面试时不占优势，但是能够很好锻炼我们的基础能力，所以花十分钟写一个吧：
import java.util.Stack;
public ListNode findFirstCommonNodeByStack(ListNode headA, ListNode headB) {
Stack<ListNode> stackA=new Stack();
Stack<ListNode> stackB=new Stack();
while(headA!=null){
stackA.push(headA);
headA=headA.next;
}
while(headB!=null){
stackB.push(headB);
headB=headB.next;
}
ListNode preNode=null;
while(stackB.size()>0 && stackA.size()>0){
if(stackA.peek()==stackB.peek()){
preNode=stackA.pop();
stackB.pop();
}else{
break;
}
}
return preNode;
}
由于在C语言基础包里没有提供栈类型，这里如果用集合需要先自己构建一个，或者引入外部包，更麻烦，因此这里我们不提供代码。
看到了吗，从一开始没啥思路到最后搞出三种方法，熟练掌握数据结构是多么重要！！
如果你想到了这三种方法中的两个，并且顺利手写并运行出一个来，面试基本就过了，至少面试官对你的基本功是满意的。
但是对方可能会再来一句：还有其他方式吗？或者说，有没有申请空间大小是O(1)的方法。方法是有的，解决方式需要使用到双指针的问题，我们放到本文最后一小节再看。
2. 判断链表是否是回文序列
LeetCode 234. 这是一道简单的，但是很经典的链表题，判断一个链表是否是回文链表。
示例 1：
输入： 1 -> 2 -> 2 -> 1
输出：true
进阶：你能否用 O（n）时间复杂度和 O（1）空间复杂度解决此题？
看到这个题你有几种思路解决，我们仍然是先将常见的数据结构和算法思想想一想，看看谁能解决问题。
方法1：将链表元素都赋值到数组中，然后可以从数组两端向中间对比。这种方法会被视为逃避链表，面试不能这么干。
方法2：将链表元素全部压栈，然后一边出栈，一边重新遍历链表，一边比较两者元素值，只要有一个不相等，那就不是。
方法3：优化方法2，先遍历第一遍，得到总长度。之后一边遍历链表，一边压栈。到达链表长度一半后就不再压栈，而是一边出栈，一边遍历，一边比较，只要有一个不相等，就不是回文链表。这样可以节省一半的空间。
方法4：优化方法3：既然要得到长度，那还是要遍历一次链表才可以，那是不是可以一边遍历一边全部压栈，然后第二遍比较的时候，只比较一半的元素呢？也就是只有一半的元素出栈， 链表也只遍历一半，当然可以。
方法5：反转链表法， 先创建一个链表newList，将原始链表oldList的元素值逆序保存到newList中，然后重新一边遍历两个链表，一遍比较元素的值，只要有一个位置的元素值不一样，就不是回文链表。
方法6：优化方法5，我们只反转一半的元素就行了。先遍历一遍，得到总长度。然后重新遍历，到达一半的位置后不再反转，就开始比较两个链表。
方法7：优化方法6，我们使用双指针思想里的快慢指针 ，fast一次走两步，slow一次走一步。当fast到达表尾的时候，slow正好到达一半的位置，那么接下来可以从头开始逆序一半的元素，或者从slow开始逆序一半的元素，都可以。
方法8：在遍历的时候使用递归来反转一半链表可以吗？当然可以，再组合一下我们还能想出更多的方法，解决问题的思路不止这些了，此时单纯增加解法数量没啥意义了。
上面这些解法中，各有缺点，实现难度也不一样，有的甚至算不上一个独立的方法，这么想只是为了开拓思路、举一反三。我们选择最佳的两种实现，其他方法请同学自行写一下试试。
这里看一下比较基本的全部压栈的解法。
将链表元素全部压栈，然后一边出栈，一边重新遍历链表，一边比较，只要有一个不相等，那就不是回文链表了，代码：
public boolean isPalindrome(ListNode head){
ListNode temp = head;
Stack<Integer> stack = new Stack();
while(temp != null){
stack.push(temp.val);
temp = temp.next;
}
//之后一边出栈，一遍比较
while(head!=null){
if(head.val != stack.pop()){
return false;
}
head = head.next;
}
return true;
}
由于在 C语言基础包里面没有提供栈类型，这里如果用集合的话需要自己先构建一个，或者引入外部包，更麻烦，因此这里不提供代码。
3. 合并有序链表
数组中我们研究过合并的问题，链表同样可以造出两个或者多个链表合并的问题。两者有相似的地方，也有不同的地方，你能找到分别是什么吗？
3.1. 合并两个有序链表
LeetCode21 将两个升序链表合并为一个新的升序链表并返回，新链表是通过拼接给定的两个链表的所有节点组成的。
本题虽然不复杂，但是很多题目的基础，解决思路与数组一样，一般有两种。一种是新建一个链表，然后分别遍历两个链表，每次都选最小的结点接到新链表上，最后排完。另外一个就是将一个链表结点拆下来，逐个合并到另外一个对应位置上去。这个过程本身就是链表插入和删除操作的拓展，难度不算大，这时候代码是否优美就比较重要了。先看下面这种：
public ListNode mergeTwoLists(ListNode list1,ListNode list2){
ListNode newHead = new ListNode(-1);
ListNode res = newHead;
while(list1!=null || list2 != null){
if(list1.val )
}
}
LeetCode21 将两个升序链表合并为一个新的升序链表并返回，新链表是通过拼接给定的两个链表的所有节点组成的。
本题虽然不复杂，但是很多题目的基础，解决思路与数组一样，一般有两种。一种是新建一个链表，然后分别遍历两个链表，每次都选最小的结点接到新链表上，最后排完。另外一个就是将一个链表结点拆下来，逐个合并到另外一个对应位置上去。这个过程本身就是链表插入和删除操作的拓展，难度不算大，这时候代码是否优美就比较重要了。先看下面这种：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode newHead=new ListNode(-1);
ListNode res=newHead;
while(list1!=null||list2!=null){
//情况1：都不为空的情况
if(list1!=null&&list2!=null){
if(list1.val<list2.val){
newHead.next=list1;
list1=list1.next;
}else if(list1.val>list2.val){
newHead.next=list2;
list2=list2.next;
}else{ //相等的情况，分别接两个链
newHead.next=list2;
list2=list2.next;
newHead=newHead.next;
newHead.next=list1;
list1=list1.next;
}
newHead=newHead.next;
//情况2：假如还有链表一个不为空
}else if(list1!=null&&list2==null){
newHead.next=list1;
list1=list1.next;
newHead=newHead.next;
}else if(list1==null&&list2!=null){
newHead.next=list2;
list2=list2.next;
newHead=newHead.next;
}
}
return res.next;
}
}
def mergeTwoLists(self, list1, list2):
phead = ListNode(0)
p = phead
while list1 and list2:
if list1.val <= list2.val:
p.next = list1
list1 = list1.next
else:
p.next = list2
list2 = list2.next
p = p.next
if list1 is not None:
p.next = list1
else:
p.next = list2
return phead.next
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
newHead->val = -1;
newHead->next = NULL;
struct ListNode* res = newHead;
while (list1 != NULL || list2 != NULL) {
// 情况1：都不为空的情况
if (list1 != NULL && list2 != NULL) {
if (list1->val < list2->val) {
newHead->next = list1;
list1 = list1->next;
} else if (list1->val > list2->val) {
newHead->next = list2;
list2 = list2->next;
} else { // 相等的情况，分别接两个链
newHead->next = list2;
list2 = list2->next;
newHead = newHead->next;
newHead->next = list1;
list1 = list1->next;
}
newHead = newHead->next;
// 情况2：假如还有链表一个不为空
} else if (list1 != NULL && list2 == NULL) {
newHead->next = list1;
list1 = list1->next;
newHead = newHead->next;
} else if (list1 == NULL && list2 != NULL) {
newHead->next = list2;
list2 = list2->next;
newHead = newHead->next;
}
}
return res->next;
上面Python代码比较简洁，但是Java和C版本代码明显比较臃肿。上面这种方式能完成基本的功能，但是所有的处理都在一个大while循环里，代码过于臃肿，我们可以将其变得苗条一些：第一个while只处理两个list 都不为空的情况，之后单独写while分别处理list1或者list2不为null的情况，也就是这样：
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode newHead = new ListNode(-1);
ListNode res = newHead;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
newHead.next = list1;
list1 = list1.next;
} else if (list1.val > list2.val) {
newHead.next = list2;
list2 = list2.next;
} else { //相等的情况，分别接两个链
newHead.next = list2;
list2 = list2.next;
newHead = newHead.next;
newHead.next = list1;
list1 = list1.next;
}
newHead = newHead.next;
}
//下面的两个while最多只有一个会执行
while (list1 != null) {
newHead.next = list1;
list1 = list1.next;
newHead = newHead.next;
}
while (list2 != null) {
newHead.next = list2;
list2 = list2.next;
newHead = newHead.next;
}
return res.next;
}
def mergeTwoLists(self, list1, list2):
phead = ListNode(0)
p = phead
while list1 and list2:
if list1.val <= list2.val:
p.next = list1
list1 = list1.next
else:
p.next = list2
list2 = list2.next
p = p.next
while list1 is not None:
p.next = list1
while list2 is not None:
p.next = list2
return phead.next
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* res = newHead;
while (list1 != NULL && list2 != NULL) {
if (list1->val < list2->val) {
newHead->next = list1;
list1 = list1->next;
} else if (list1->val > list2->val) {
newHead->next = list2;
list2 = list2->next;
} else {
newHead->next = list2;
list2 = list2->next;
newHead = newHead->next;
newHead->next = list1;
list1 = list1->next;
}
newHead = newHead->next;
}
while (list1 != NULL) {
newHead->next = list1;
list1 = list1->next;
newHead = newHead->next;
}
while (list2 != NULL) {
newHead->next = list2;
list2 = list2->next;
newHead = newHead->next;
}
return res->next;
}
拓展 进一步优化代码
进一步分析，我们发现两个继续优化的点，一个是上面第一个大while里有三种情况，我们可以将其合并成两个，如果两个链表存在相同元素，第一次出现时使用if (l1.val <= l2.val)来处理，后面一次则会被else处理掉，什么意思呢？我们看一个序列。
假如list1为{1, 5, 8, 12}，list2为{2, 5, 9, 13}，此时都有一个node(5)。当两个链表都到5的位置时，出现了list1.val == list2.val，此时list1中的node(5)会被合并进来。然后list1继续向前走到了node(8)，此时list2还是node(5)，因此就会执行else中的代码块。这样就可以将第一个while的代码从三种变成两种，精简了很多。
第二个优化是后面两个小的while循环，这两个while最多只有一个会执行，而且由于链表只要将链表头接好，后面的自然就接上了，因此循环都不用写，也就是这样：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2){
ListNode node = new ListNode();
ListNode res = node;
while(list1 != null && list2 !=null){
if(list1.val <= list2.val){
node.next = list1;
list1 = list1.next;
}else{
node.next = list2;
list2 = list2.next;
}
node = node.next;
}
node.next = list1 == null ? list2:list1;
return res.next;
}
}
def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
prehead = ListNode(-1)
prev = prehead
while list1 != None and list2 != None:
if list1.val <= list2.val:
prev.next = list1
list1 = list1.next
else:
prev.next = list2
list2 = list2.next
prev = prev.next
# 最多只有一个还未被合并完，直接接上去就行了,这是链表合并比数组合并方便的地方
if list1 == None:
prev.next = list2
else:
prev.next = list1
return prehead.next
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode* prehead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* prev = prehead;
while (list1 != NULL && list2 != NULL) {
if (list1->val <= list2->val) {
prev->next = list1;
list1 = list1->next;
} else {
prev->next = list2;
list2 = list2->next;
}
prev = prev->next;
}
prev->next = list1 == NULL ? list2 : list1;
return prehead->next;
}
这种方式很明显更高级，但是面试时很难考虑周全，如果面试的时候遇到了，建议先用上面第二种写法写出来，面试官满意之后，接着说“我还可以用更精简的方式来解决这个问题”，然后再写尝试写第三种，这样不但不用怕翻车，还可以锦上添花。
3.2. 合并 K 和链表
合并k个链表，有多种方式，例如堆、归并等等。如果面试遇到，我倾向先将前两个合并，之后再将后面的逐步合并进来，这样的的好处是只要将两个合并的写清楚，合并K个就容易很多，现场写最稳妥：
public static ListNode mergeKLists(ListNode[] lists){
ListNode res = null;
for(ListNode list:lists){
res = merageTwoLists(res,list);
}
}
public ListNode mergeTwoLists(ListNode list1, ListNode list2){
ListNode node = new ListNode(-1);
ListNode res = node;
while(list1 != null && list2 !=null){
if(list1.val <= list2.val){
node.next = list1;
list1 = list1.next;
}else{
node.next = list2;
list2 = list2.next;
}
node = node.next;
}
node.next = list1 == null ? list2:list1;
return res.next;
}
class MergeKLists:
def mergeKLists(self, lists):
def mergeTwoLists(a, b):
merge = ListNode(-1)
head = merge
while a and b:
if a.val > b.val:
head.next = b
b = b.next
else:
head.next = a
a = a.next
head = head.next
head.next = a if a else b
return merge.next
if len(lists) == 0:
return None
res = None
for i in range(0, len(lists)):
res = mergeTwoLists(res, lists[i])
return res
struct ListNode* mergeKLists(struct ListNode* lists[], int size) {
struct ListNode* res = NULL;
for (int i = 0; i < size; i++) {
res = mergeTwoLists(res, lists[i]);
}
return res;
}
3.3. 一道很无聊的好题目
LeetCode1669：给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。请你将 list1 中下标从a到b的节点删除，并将list2 接在被删除节点的位置。
1669题的意思就是将list1中的[a,b]区间的删掉，然后将list2接进去，如下图所示：
你觉得难吗？如果这也是算法的话，我至少可以造出七八道题，例如：
（1）定义list1的[a,b]区间为list3，将list3和list2按照升序合并成一个链表。
（2）list2也将区间[a,b]的元素删掉，然后将list1和list2合并成一个链表。
（3）定义list2的[a,b]区间为list4，将list2和list4合并成有序链表。
看到了吗？掌握基础是多么重要，我们自己都能造出题目来。这也是为什么算法会越刷越少，因为到后面会发现套路就这样，花样随便变，以不变应万变就是我们的宗旨。
具体到这个题，按部就班遍历找到链表1保留部分的尾节点和链表2的尾节点，将两链表连接起来就行了。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
ListNode preA = list1;
for(int i = 0; i < a - 1;i++){
preA = preA.next;
}
ListNode preB = preA;
for(int i = 0; i < b - a + 2;i++){
preB = preB.next;
}
preA.next = list2;
while(list2.next != null){
list2 = list2.next;
}
list2.next = preB;
return list1;
}
}
def mergeInBetween(self, list1, a, b, list2):
dummy = ListNode(0)
dummy.next = list1
tmp1 = tmp2 = dummy
l1, l2 = a, b + 2
while l1:
tmp1 = tmp1.next
l1 -= 1
while l2:
tmp2 = tmp2.next
l2 -= 1
tmp1.next = list2
while list2.next:
list2 = list2.next
list2.next = tmp2
return dummy.next
struct ListNode* mergeInBetween(struct ListNode* list1, int a, int b, struct ListNode* list2){
struct ListNode* pre1 = list1;
struct ListNode* post1 = list1;
struct ListNode* post2 = list2;
int i = 0, j = 0;
// 寻找list1中的节点pre1和post1
while (pre1 != NULL && post1 != NULL && j < b) {
if (i != a - 1) {
pre1 = pre1->next;
i++;
}
if (j != b) {
post1 = post1->next;
j++;
}
}
post1 = post1->next;
// 寻找list2的尾节点
while (post2->next != NULL) {
post2 = post2->next;
}
// 链1尾接链2头，链2尾接链1后半部分的头
pre1->next = list2;
post2->next = post1;
return list1;
}
这里需要留意题目中是否有开闭区间的情况，例如如果是从a到b，那就是闭区间[a,b]。还有的会说一个开区间 (a,b)，此时是不包括a和b两个元素，只需要处理a和b之间的元素就可以了。比较特殊的是进行分段处理的时候，例如K个一组处理，此时会用到左闭右开区间，也就是这样子[a,b)，此时需要处理a，但是不用处理b，b是在下一个区间处理的。此类题目要非常小心左右边界的问题。
除了使用栈，我们也可以使用链表反转的方法来做，而且可以只反转一半的链表，之后一边遍历剩下的部分一边来比较，该方式我们放到链表反转的白银挑战里。感兴趣的同学可以提前看一下。
4. 双指针专题
4.1. 寻找中间节点
LeetCode876 给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例1
输入：[1,2,3,4,5]
输出：此列表中的结点 3
示例2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4
这个问题用经典的快慢指针可以轻松搞定，用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。
这里还有个问题，就是偶数的时候该返回哪个，例如上面示例2返回的是4， 而3貌似也可以，那该使用哪个呢？如果我们使用标准的快慢指针就是后面的4，而在很多数组问题中会是前面的3，想一想为什么会这样。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head,fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
class MiddleNode:
def middleNode(self, head):
if head is None:
return None
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
if __name__ == '__main__':
# 先构造题目要求的链表,简单构造即可
nums = [1, 2, 3, 4, 5, 6]
list = init_list(nums)
middleNode = MiddleNode()
node = middleNode.middleNode(list)
print node.val
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
4.2. 寻找倒数第 k 个元素
这也是经典的快慢双指针问题，先看要求：
输入一个链表，输出该链表中倒数第k个节点。本题从1开始计数，即链表的尾节点是倒数第1个节点。
示例
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
这里也可以使用快慢双指针，我们先将fast 向后遍历到第 k+1 个节点， slow仍然指向链表的第一个节点，此时指针fast 与slow 二者之间刚好间隔 k 个节点。之后两个指针同步向后走，当 fast 走到链表的尾部空节点时，slow 指针刚好指向链表的倒数第k个节点。
这里需要特别注意的是链表的长度可能小于k，寻找k位置的时候必须判断fast是否为null，这是本题的关键问题之一，最终代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head,fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
class GetKthFromEnd:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
former, latter = head, head
for _ in range(k):
if not former: return
former = former.next
while former:
former, latter = former.next, latter.next
return latter
4.3. 旋转链表
Leetcode61.先看题目要求：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
示例1:
输入：head = [1,2,3, 4,5], k = 2
输出：[4,5,1,2,3]
这个题有多种解决思路，首先想到的是根据题目要求硬写，但是这样比较麻烦，也容易错。这个题是否在数组里见过类似情况？
观察链表调整前后的结构，我们可以发现从旋转位置开始，链表被分成了两条，例如上面的{1,2,3}和{4,5}，这里我们可以参考上一题的倒数K的思路，找到这个位置，然后将两个链表调整一下重新接起来就行了。具体怎么调整呢？脑子里瞬间想到两种思路：
第一种是将整个链表反转变成{5,4,3,2,1}，然后再将前K和N-K两个部分分别反转，也就是分别变成了{4,5}和{1,2,3},这样就轻松解决了。这个在后面学习了链表反转之后，请读者自行解决。
第二种思路就是先用双指针策略找到倒数K的位置，也就是{1,2,3}和{4,5}两个序列，之后再将两个链表拼接成{4,5,1,2,3}就行了。具体思路是：
因为k有可能大于链表长度，所以首先获取一下链表长度len，如果然后k=k % len，如果k == 0，则不用旋转，直接返回头结点。否则：
1.快指针先走k步。
2.慢指针和快指针一起走。
3.快指针走到链表尾部时，慢指针所在位置刚好是要断开的地方。把快指针指向的节点连到原链表头部，慢指针指向的节点断开和下一节点的联系。
4.返回结束时慢指针指向节点的下一节点。
public ListNode rotateRight(ListNode head,int k){
if(head == null || k == 0){
return head;
}
ListNode temp = head;
ListNode fast = head;
ListNode slow = head;
int len = 0;
//当头结点不为空的时候一直遍历，然后 len++
// 遍历完之后 head 为空
while(head != null){
head = head.next;
len++;
}
if((k % len) == 0){
return temp;
}
//从这里 fast 开始移动，取模是为了防止 k 大于 len 的情况出现
while((k % len) > 0){
k--;
fast = fast.next;
}
while(fast.next != null){
fast = fast.next;
slow = slow.next;
}
ListNode res = slow.next;
slow.next = null;
fast.next = temp;
return res;
}
如果使用链表反转怎么做呢？学习完后面《链表反转以及相关问题》之后，再来看。
struct ListNode* rotateRight(struct ListNode* head, int k) {
if (head == NULL || k == 0) {
return head;
}
//这里三个变量都指向链表头结点
struct ListNode* temp = head;
struct ListNode* fast = head;
struct ListNode* slow = head;
int len = 0;
//这里head先走一遍，统计出链表的元素个数，完成之后head就变成null了
while (head != NULL) {
head = head->next;
len++;
}
if (k % len == 0) {
return temp;
}
// 从这里开始fast从头结点开始向后走
//这里使用取模，是为了防止k大于len的情况
//例如，如果len=5，那么k=2和7，效果是一样的
while ((k % len) > 0) {
k--;
fast = fast->next;
}
// 快指针走了k步了，然后快慢指针一起向后执行
// 当fast到尾结点的时候，slow刚好在倒数第K个位置上
while (fast->next != NULL) {
fast = fast->next;
slow = slow->next;
}
struct ListNode* res = slow->next;
slow->next = NULL;
fast->next = temp;
return res;
}
事实上，本题不用这么麻烦，假如我们要找倒数第K个，那就是要找正数第Len-k+1个。因此可以先遍历一遍，计算出LEN，然后直接通过计算得到需要走的步数，只会从头开始遍历，到第Len-k+1即可。当然，我们也要通过取模来计算防止K越界。我们这里只看一下Python的实现：
class RotateRight:
def rotateRight(self, head, k):
if head is None or head.next is None:
return head
num = 0
basic_head = head
//统计长度
while head:
if head.next is None:
head.next = basic_head
num += 1
break
num += 1
head = head.next
# print(num)
//这里直接计算需要向前走多少步
xx = num - (k % num)
for i in range(xx):
if i == (xx - 1):
flag = basic_head
basic_head = basic_head.next
flag.next = None
break
basic_head = basic_head.next
return basic_head
if __name__ == '__main__':
# 先构造题目要求的链表,简单构造即可
nums = [1, 2, 3, 4, 5]
rotateRight = RotateRight()
list = init_list(nums)
node = rotateRight.rotateRight(list, 2)
5. 删除链表元素专题
5.1. 删除特定节点
先看一个简单的问题，LeetCode 203：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点 。
示例1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
我们前面说过，我们删除节点cur时，必须知道其前驱pre节点和后继next节点，然后让pre.next=next。这时候cur就脱离链表了，cur节点会在某个时刻被gc回收掉。
对于删除，我们注意到首元素的处理方式与后面的不一样。为此，我们可以先创建一个虚拟节点 dummyHead，使其指向head，也就是dummyHead.next=head，这样就不用单独处理首节点了。
完整的步骤是：
●1.我们创建一个虚拟链表头dummyHead，使其next指向head。
●2.开始循环链表寻找目标元素，注意这里是通过cur.next.val来判断的。
●3.如果找到目标元素，就使用cur.next = cur.next.next;来删除。
●4.注意最后返回的时候要用dummyHead.next，而不是dummyHead。
代码实现过程：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null){
return head;
}
ListNode temp = new ListNode(0);
temp.next = head;
ListNode cur = temp;
while(cur.next != null){
if(cur.next.val == val){
cur.next = cur.next.next;
continue;
}
cur = cur.next;
}
return temp.next;
}
}
class RemoveElements:
def removeElements(self, head, val):
while head and head.val == val:
head = head.next
if head is None:
return head
node = head
while node.next:
if node.next.val == val:
node.next = node.next.next
else:
node = node.next
return head
if __name__ == '__main__':
array = [1, 2, 6, 3, 4, 5, 6]
val = 6
head = init_list(array)
removeElements = RemoveElements()
node = removeElements.removeElements2(head, 6)
print node
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode* dummyHead = (struct ListNode*) malloc(sizeof(struct ListNode));
dummyHead->val = 0;
dummyHead->next = head;
struct ListNode* cur = dummyHead;
while (cur->next != NULL) {
if (cur->next->val == val) {
struct ListNode* temp = cur->next;
cur->next = cur->next->next;
free(temp);
} else {
cur = cur->next;
}
}
struct ListNode* newHead = dummyHead->next;
free(dummyHead);
return newHead;
}
我们继续看下面这两个题，其实就是一个题：
LeetCode 19. 删除链表的倒数第 N 个节点
LeetCode 1474. 删除链表 M 个节点之后的 N 个节点。
既然要删除倒数第N个节点，那一定要先找到倒数第N个节点，前面已经介绍过，而这里不过是找到之后再将其删除。
5.2. 删除倒数第 n 个结点
LeetCode19题要求：给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。进阶：你能尝试使用一趟扫描实现吗？
我们前面说过，遇到一个题目可以先在脑子里快速过一下常用的数据结构和算法思想，看看哪些看上去能解决问题。为了开拓思维，我们看看能怎么做：
第一种方法：先遍历一遍链表，找到链表总长度L，然后重新遍历，位置L-N+1的元素就是我们要删的。
第二种方法：貌似栈可以，先将元素全部压栈，然后弹出第N个的时候就是我们要的是不？OK，又搞定一种方法。
第三种方法：我们前面提到可以使用双指针 来寻找倒数第K，那这里同样可以用来寻找要删除的问题。
上面三种方法，第一种比较常规，第二种方法需要开辟一个O(n)的空间，还要考虑栈与链表的操作等，不中看也不中用。第三种方法一次遍历就行，用双指针也有逼格。接下来我们详细看一下第一和三两种。方法1：计算链表长度
首先从头节点开始对链表进行一次遍历，得到链表的长度 L。随后我们再从头节点开始对链表进行一次遍历，当遍历到第L−n+1 个节点时，它就是我们需要删除的节点。代码如下：
public ListNode removeNthFromEnd(ListNode head,int n){
ListNode dummy = new ListNode(0);
dummy.next = head;
int length = getLength(head);
ListNode cur =dummy;
for(int i = 1; i < length - n + 1;i++){
cur = cur.next;
}
cur.next = cur.next.next;
ListNode ans = dummy.next;
return ans;
}
public int getLength(ListNode head){
int length = 0;
while(head != null){
head = head.next;
length++;
}
return length; e
}
class RemoveNthFromEnd:
def removeNthFromEnd(self, head, n):
def getLength(head):
length = 0
while head:
length += 1
head = head.next
return length
dummy = ListNode(0, head)
length = getLength(head)
cur = dummy
for i in range(1, length - n + 1):
cur = cur.next
cur.next = cur.next.next
return dummy.next
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode* dummy = (struct ListNode*) malloc(sizeof(struct ListNode));
dummy->val = 0;
dummy->next = head;
int length = getLength(head);
struct ListNode* cur = dummy;
for (int i = 1; i < length - n + 1; ++i) {
cur = cur->next;
}
struct ListNode* temp = cur->next;
cur->next = cur->next->next;
free(temp);
struct ListNode* ans = dummy->next;
free(dummy);
return ans;
}
int getLength(struct ListNode* head) {
int length = 0;
while (head != NULL) {
++length;
head = head->next;
}
return length;
}
法2：双指针
我们定义first和second两个指针，first先走N步，然后second再开始走，当first走到队尾的时候，second就是我们要的节点。代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = head;
ListNode slow = dummy;
for(int i = 0;i < n;i++){
fast = fast.next;
}
while(fast!=null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
def removeNthFromEnd(self, head, n):
dummy = ListNode(0, head)
fast = head
slow = dummy
for i in range(n):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode* dummy = (struct ListNode*) malloc(sizeof(struct ListNode));
dummy->val = 0;
dummy->next = head;
struct ListNode* first = head;
struct ListNode* second = dummy;
for (int i = 0; i < n; ++i) {
first = first->next;
}
while (first != NULL) {
first = first->next;
second = second->next;
}
struct ListNode* temp = second->next;
second->next = second->next->next;
free(temp);
struct ListNode* ans = dummy->next;
free(dummy);
return ans;
}
5.3. 删除重复元素
5.3.1. 重复元素保留一个
我们继续看关于结点删除的题：
LeetCode 83 存在一个按升序排列的链表，请你删除所有重复的元素，使每个元素只出现一次。
LeetCode 82 存在一个按升序排列的链表，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。
两个题其实是一个，区别就是一个要将出现重复的保留一个，一个是只要重复都不要了，处理起来略有差别。LeetCode 1836是在82的基础上将链表改成无序的了，难度要增加不少，感兴趣的同学请自己研究一下。
5.3.1 重复元素保留一个
LeetCode83 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素只出现一次 。返回同样按升序排列的结果链表。
示例1：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。具体地，我们从指针 cur 指向链表的头节点，随后开始对链表进行遍历。如果当前 cur 与cur.next 对应的元素相同，那么我们就将cur.next 从链表中移除；否则说明链表中已经不存在其它与cur 对应的元素相同的节点，因此可以将 cur 指向 cur.next。当遍历完整个链表之后，我们返回链表的头节点即可。
另外要注意的是 当我们遍历到链表的最后一个节点时，cur.next 为空节点，此时要加以判断，上代码：
public ListNode deleteDuplicates(ListNode head){
if(head == null){
return head;
}
ListNode cur = head;
while(cur.next != null){
if(cur.val == cur.next.val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return head;
}
class DeleteDuplicates:
def deleteDuplicates(self, head):
if not head:
return head
cur = head
while cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next
else:
cur = cur.next
return head
if __name__ == '__main__':
head = [1, 1, 2, 3, 3]
list = init_list(head)
deleteDuplicates = DeleteDuplicates()
node = deleteDuplicates.deleteDuplicates(list)
print node
struct ListNode* deleteDuplicates(struct ListNode* head) {
if (head == NULL) {
return head;
}
struct ListNode* cur = head;
while (cur->next != NULL) {
if (cur->val == cur->next->val) {
struct ListNode* temp = cur->next;
cur->next = cur->next->next;
free(temp);
} else {
cur = cur->next;
}
}
return head;
}
5.3.2. 重复元素都不要
LeetCode82：这个题目的要求与83的区别仅仅是重复的元素都不要了。例如：
示例1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
当一个都不要时，链表只要直接对cur.next 以及 cur.next.next 两个node进行比较就行了，这里要注意两个node可能为空，稍加判断就行了。
public ListNode deleteDuplicates(ListNode head){
if(head == null){
return head;
}
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while(cur.next != null && cur.next.next != null){
if(cur.next.val == cur.next.next.val){
int x= cur.next.val;
while(cur.next != null && cur.next.val == x){
cur.next = cur.next.next;
}
}else{
cur = cur.next;
}
}
return dummy.next;
}
class DeleteDuplicates:
def deleteDuplicates(self, head) :
if not head:
return head
dummy = ListNode(0, head)
cur = dummy
while cur.next and cur.next.next:
if cur.next.val == cur.next.next.val:
x = cur.next.val
while cur.next and cur.next.val == x:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.next
struct ListNode* deleteDuplicates(struct ListNode* head) {
if (head == NULL) {
return head;
}
struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
dummy->val = 0;
dummy->next = head;
struct ListNode* cur = dummy;
while (cur->next != NULL && cur->next->next != NULL) {
if (cur->next->val == cur->next->next->val) {
int x = cur->next->val;
while (cur->next != NULL && cur->next->val == x) {
struct ListNode* temp = cur->next;
cur->next = cur->next->next;
free(temp);
}
} else {
cur = cur->next;
}
}
return dummy->next;
}
如果链表是未排序的该怎么办呢？如果先排序再操作代价太高了，感兴趣的同学可以继续研究一下。
6. 再论第一个公共子节点问题
6.1. 差和双指针
设「第一个公共节点」为 node ，「链表 headA」的节点数量为 a ，「链表 headB」的节点数量为 b ，「两链表的公共尾部」的节点数量为 c，则有：
头节点 headA 到 node 前，共有 a−c 个节点；
头节点 headB 到 node 前，共有 b−c个节点；
考虑构建两个节点指针 A，B ，分别指向两链表头节点 headA , headB ，做如下操作：
- 指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：a + (b - c)
- 指针 B 先遍历完链表 headB。再开始遍历链表 headA，当走到 node 的时候，一共走了 b + （a - c）
如下式所示，此时指针 A，B 重合，并且有两种情况：a+(b−c)=b+(a−c)
- 若两链表 有 公共尾部（即 c > 0）:指针 A，B 同时指向【第一个公共节点】 node.
- 若两链表 无 公共尾部（即 c = 0）：指针 A，B 同时指向 null。
因此返回 A 就可以了。
如下图所示：a = 5 ， b = 3, c= 2 示例的算法执行过程。
以下是对应的代码，我个人推荐是这个代码，因为其双指针思想更加巧妙一点。
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A = headA,B = headB;
while(A!=B){
A = A != null ? A.next:headB;
B = B != null ? B.next:headA;
}
return A;
}
}
6.2. 拼接两个字符串
先看一下下面的链表 A 和 B：
A：0-1-2-3-4-5
B ：a - b -4 -5
如果分别拼接成 AB 和 BA 会怎么样呢？
AB:0-1-2-3-4-5-A-B-4-5
BA:a-b-4-5-0-1-2-3-4-5
我们可以发现，拼接从最后的4开始，两个链表是一样的，自然 4 就是我们要找的节点，所以可以通过拼接的方式来寻找交点。这么做的道理是什么？我们从几何的角度来分析。我们假定A和B有相交的位置，以交点为中心，可以将两个链表分别分为left_a和right_a，left_b和right_b这样四个部分，并且right_a和right_b是一样的，这时候我们拼接AB和BA就是这样的结构：
我们说 right_a 和 right_b 是一样的，那这个时候分别遍历AB和BA是不是从某个位置开始恰好就找到了相交的点了？
这里还可以进一步优化，如果建立新的链表太浪费空间了，我们只要在每个链表访问完了之后，调整到一下链表的表头继续遍历就行了，于是代码就出来了：
这里很多人会对为什么循环体里if(p1!=p2)这个 判断有什么作用，我们在代码后面解释
public ListNode findFirstCommonNode(ListNode pHead1,ListNode phead2){
if(pHead1 == null || pHead2 == null){
return null;
}
ListNode p1 = pHead1;
ListNode p2 = phead2;
while(p1 != p2){
p1 = p1.next;
p2 = p2.next;
if(p1 != p2){
if(p1 == null){
p1=pHead2;
}
if(p2 == null){
p2 =pHead1;
}
}
}
}
这种方式使用了两个指针，其实和第一种算法是差不多的，也可以算作双指针。
接下来来解释一下为什么循环体里面需要判断 p1 != p2。简单来说，如果序列不存在交集的时候就陷入死循环了，例如 list1 是 1 2 3，list2 是 4 5，很明显，如果不加判断的话，list1 和 list2 会不断陷入循环，导致出不来。
阅读量：979
点赞量：0
收藏量:0