面试高频算法题之链表
链表
全文概览
文章图片
如果需要本文的PDF文档，请联系作者。或者关注公众【程序员学长】获取。
链表基础知识
链表的分类
链表是一种通过指针串联在一起的线性结构，主要分为单链表、双向链表和循环链表。
单链表
单链表中每一个节点是由两部分组成，一个是数据域、一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域为空。
文章图片
双向链表
双向链表中的每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。双向链表既可以向前查询也可以向后查询。
文章图片
单向循环链表
单向循环链表是指首尾相连的单链表。
文章图片
双向循环链表
双向循环链表是指首尾相连的双向链表。
文章图片
链表的定义
我们在刷LeetCode的时候，由于链表的节点都默认定义好了，直接用就行了，但是在面试的时候，一旦要手写链表代码时，节点的定义是大家容易犯错的地方，所有我们来看一下定义链表节点的方式。
#单链表
class ListNode(object):
def __init__(self, x):
#数据域
self.val = x
#指针域
self.next = None链表的操作
单链表的删除操作 删除链表中的q节点，只需要执行p->next=q->next，即让p的指针域指向q的下一个节点。
文章图片
向单链表中增加一个节点 在节点p后增加一个节点q，只需要执行q->next=p->next，p->next=q即可，这里一定要注意执行的先后顺序。如果先执行p->next=q，那么原链表的p->next的信息就丢失了。
文章图片
解题有妙招
引入哑结点 哑结点也叫做哨兵节点，对于链表相关的题目，为了方便处理边界条件，一般我们都会引入哑结点来方便求解。首先我们来看一下什么是哑结点，哑结点是指数据域为空，指针域指向链表头节点的节点，它是为了简化边界条件而引入的。下面我们来看一个具体的例子，例如要删除链表中的某个节点操作。常见的删除链表的操作是找到要删元素的前一个元素，假如我们记为 pre。我们通过：pre->next=pre->next->next来执行删除操作。如果此时要删除的是链表的第一个结点呢？就不能执行这个操作了，因为链表的第一个结点的前一个节点不存在，为空。如果此时你设置了哑结点，那么第一个结点的前一个节点就是这个哑结点。这样如果你要删除链表中的任何一个节点，都可以通过pre->next=pre->next->next的方式来进行，这就简化的代码的逻辑。
文章图片
双指针法 在求解链表相关的题目时，双指针也是非常常用的思想，例如对于求解链表有环问题时，我们申请两个指针，以一快一慢的速度在链表上行走，等他们相遇时，就可以知道链表是否有环；或者在求链表的倒数k个节点时，申请两个指针，一个指针先走k步，然后两个指针再同时向后移动，当先走的那个指针走到链表的末尾时，另一个指针恰好指向了倒数第k个节点。
反转链表 LeetCode206. 反转链表
问题描述
给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
示例:
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]分析问题
首先，我们按照题目的要求，先把图画出来，然后再分析。
文章图片
从图中我们可以看到，反转前和反转后指针的指向发生了反转。所以，我们在实现的过程中，我们可以通过调整链表的指针来达到反转链表的目的。
- 我们定义两个指针pre和cur。pre表示已反转部分的头结点，cur表示还没有反转部分的头结点。开始时cur=head，pre=None
- 每次让cur->next=pre，实现一次局部反转。
- 局部反转完成后，cur和pre同时向前移动一位。
- 循环上述过程，直到链表反转完成。
文章图片
代码实现
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = nextclass Solution:
def reverse(self, head):
cur = head
#初始化时，pre为None
pre = None
while cur:
next=cur.next
cur.next = pre
pre = cur
cur = next
return prehead=ListNode(1,None)
cur=head
for i in range(2,6):
tmp=ListNode(i,None)
cur.next=tmp
cur=cur.nexts=Solution()
pre=s.reverse(head)while pre!=None:
print(pre.val)
pre=pre.next合并两个有序链表 LeetCode21. 合并两个有序链表
问题描述
输入两个单调递增的链表，输出两个链表合成后的链表，我们需要合成后的链表满足单调不减规则。
示例：
输入: {1,3,5},{2,4,6}
返回值: {1,2,3,4,5,6}
分析问题
既然给定的两个链表都是有序的，那么我们可以判断两个链表的头结点的值的大小，将较小值的结点添加到结果中，然后将对应链表的结点指针后移一位，循环往复，直到有一个链表为空为止。
由于链表是有序的，所以循环终止时，那个非空的链表中的元素都比前面已经合并的链表中的元素大，所以，我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可。
首先我们需要先创建一个哨兵节点，然后将prehead指向链表l1和l2中比较小的一个。如果相等的话，指向任意一个即可。然后将较小值对应的链表的指针后移一位。
文章图片
文章图片
文章图片
文章图片
我们下面来看一下代码实现。
def mergeTwoLists(self, l1, l2):
#合并后链表的哨兵结点
head=ListNode(-1,None)
pre=head
#循环遍历，将两个链表中的较小值插入到合并后的链表中
while l1 and l2:
if l1.val <= l2.val:
pre.next=l1
l1=l1.next
else:
pre.next=l2
l2=l2.next
pre=pre.next
#将剩余的非空链表插入到合并链表的后面
if l1:
pre.next=l1
else:
pre.next=l2return head.next其实，我们这里也可以使用递归的方式来实现。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = nextclass Solution:
def mergeTwoLists(self, l1, l2):
#链表l1为空，不需要合并，直接返回l2
if(l1==None):
return l2
#同理，l2为空，直接返回l1即可
if(l2==None):
return l1if(l1.val<=l2.val):
l1.next=self.mergeTwoLists(l1.next,l2)
return l1
else:
l2.next=self.mergeTwoLists(l1,l2.next)
return l2问题升级
LeetCode23. 合并K个升序链表
下面，我们来把问题升级一下，将两个有序链表合并改成多个有序链表合并，我们来看一下题目。
给定一个有序链表， 其中每个节点也表示有一个有序链表。结点包含两个类型的指针：
- 指向主链表中下一个结点的指针。
- 指向以此结点为头的链表。
4 ->9 -> 15 -> 19
||||
7131828
|||
82137
|
20 实现函数flatten()，该函数用来将链表扁平化成单个链表。例如上面的链表，输出链表为
4 -> 7 -> 8 -> 9 -> 13 -> 15 -> 18 ->19 -> 20 -> 21 -> 28 -> 37 题目要求我们把二维有序链表合并成一个单链表，我们来把问题简化一下，假设主链表只有两个节点，即这个二维链表变成如下所示。
4 ->9
||
713旋转一下4 -> 7 -> 8 -> 20
|---------->|
89 -> 13
|
20这不就是我们上面讲的两个有序链表合并吗？那如果主链表有多个节点呢？我们可以使用归并的思想，逐个去合并就好了，如下图所示。
文章图片
下面我们来看一下代码如何实现。
class ListNode:
def __init__(self, val=0, right=None, down=None):
self.val = val
self.right = right
self.down = downclass Solution:
def mergeTwoLists(self, l1, l2):
#如果有一个链表为空，则合并后的链表就是另外一个
if(l1==None):
return l2
if(l2==None):
return l1if(l1.val<=l2.val):l1.down=self.mergeTwoLists(l1.down,l2)
return l1
else:
l2.down=self.mergeTwoLists(l1,l2.down)
return l2def flatten(self,root):
if root== None or root.right == None:
return root
#把root->right 看作是已经有序的单链表，
#然后通过递归来进行归并
return self.mergeTwoLists(root, self.flatten(root.right))链表中的节点每k个一组翻转 问题描述
LeetCode25. K 个一组翻转链表
将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表。如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样。你不能更改节点中的值，只能更改节点本身。
例如：
给定的链表是：1 -> 2 -> 3 -> 4 -> 5
对于 k=2，你应该返回 2 -> 1 -> 4 -> 3 -> 5
对于 k=3， 你应该返回 3 -> 2 -> 1 -> 4 -> 5
分析问题
我们把这个问题进行拆分。
- 我们首先将链表按照k个一组进行分组。对于最后一组，有可能元素个数不满足k个。
- 对于每一个分组，我们去判断元素的个数是否为k，如果是k的话，我们进行反转，否则不需要进行反转。
文章图片
我们下面来看一下代码实现。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = nextclass Solution:
#反转链表，并且返回链表头和尾
def reverse(self, head, tail):
prev = tail.next
p = head
while prev != tail:
next = p.next
p.next = prev
prev = p
p = next
return tail, headdef reverseKGroup(self, head, k):
#初始化一个哨兵节点，避免临界条件复杂的判断
prehead = ListNode(0)
#哨兵节点指向头结点
prehead.next = head
pre = preheadwhile head:
tail = pre
#查看剩余部分长度是否大于等于k
for i in range(k):
tail = tail.next
#如果剩余长度小于k,则不需要反转，直接返回
if not tail:
return prehead.next
#tail指向子链表的尾部
#所以next指向下一个子链表的头部
next = tail.next
#将链表进行反转，并返回链表头和尾
head, tail = self.reverse(head, tail)
#把子链表重新接回原链表
pre.next = head
tail.next = next
pre = tail
head = tail.nextreturn prehead.next判断链表是否有环 问题描述
LeetCode141. 环形链表
给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
示例：
输入：head = [-1,-7, 7,-4, 9, 6, -5, -2], pos = 3
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
分析问题
拿到这个问题，我们最直观的想法就是在遍历结点的过程中去标记一下这个结点是否已经被访问过。如果被访问过，那么就代表该链表有环，直接返回。如果没有被访问过，我们就标记一下，然后接着去遍历下一个结点，直到遍历完整个链表为止。下面我们来看一下代码的实现。
def hasCycle(self, head):
tags = set()
while head:
#表示已经被访问过了，代表有环
if head in tags:
return True
tags.add(head)
head = head.next
return False我们可以知道该算法的时间复杂度和空间复杂度都是O(n)。那我们有更好的解法吗？
优化
你可以这么思考，当有两名同学在操场上以不同的速度进行跑步，它们最终肯定会相遇。因为操场是环形的，如果在直线上跑，那他们肯定不会相遇。
我们假设同学1以速度1在跑，同学2以速度2在跑。
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
下面我们来看一下代码如何实现。
def hasCycle(self, head):
#如果链表为空或者链表只有一个结点
#直接返回false,因为不可能有环
if not head or not head.next:
return False
#快慢指针
slow = fast = head
start = Truewhile slow != fast || start:
start=False
if not fast or not fast.next:
return False
slow = slow.next
fast = fast.next.nextreturn True我们这里引入了一个变量start表示是否是起跑。
可以看到该算法的空间复杂度降低为O(1)。
链表中环的入口结点 问题描述
LeetCode 剑指 Offer II 022. 链表中环的入口节点
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
分析问题
拿到这个问题，我们最直观的想法就是在遍历结点的过程中去标记一下这个结点是否已经被访问过。如果被访问过，就代表这个结点是链表中环的入口点，我们直接返回就好。如果没有被访问过，我们就标记一下，然后接着去遍历下一个结点，直到遍历完整个链表为止。下面我们来看一下代码的实现。
def EntryNodeOfLoop(self, pHead):
tags = set()
while pHead:
#表示已经被访问过了，代表有环
if pHead in tags:
return pHead
tags.add(pHead)
pHead = pHead.next
return None我们可以看到该算法的时间复杂度和空间复杂度都是O(n)。
优化
我们这里也可以采用快慢指针来求解，就和上一题的解法类似，我们来看一下。
我们可以使用两个指针fast和slow。他们都从链表的头部开始出发，slow每次都走一步，即slow=slow->next，而fast每次走两步，即fast=fast->next->next。如果链表中有环，则fast和slow最终会在环中相遇。
我们假设链表中环外的长度为a，show指针进入环后又走了b的距离与fast相遇，此时fast指针已经绕着环走了n圈。所以快指针一共走了a+n(b+c)+b=a+(n+1)b+nc的距离，我们知道快指针每次走2步，而慢指针每次走一步，所以，我们可以得出快指针走的距离是慢指针的两倍，即a+(n+1)b+nc=2(a+b)，所以a=c+(n-1)(b+c)。这里你会发现：从相遇点到入环的距离c，再加上n-1圈的环长，恰好等于从链表头部到入环点的距离。
因此，当发现slow和fast相遇时，我们再额外使用一个指针ptr指向链表头部，然后它和slow指针每次都向后移动一个位置。最终，他们会在入环点相遇。
Tips: 你也许会有疑问，为什么慢指针在第一圈没走完就会和快指针相遇呢？我们来看一下，首先，快指针会率先进入环内。然后，当慢指针到达环的入口时，快指针在环中的某个位置，我们假设此时快指针和慢指针的距离为x，若x=0，则表示在慢指针刚入环时就相遇了。我们假设环的长度为n，如果看成快指针去追赶慢指针，那么快指针需要追赶的距离为n-x。因为快指针每次都比慢指针多走一步，所以一共需要n-x次就能追上慢指针，在快指针遇上慢指针时，慢指针一共走了n-x步，其中x>=0，所以慢指针走的路程小于等于n，即走不完一圈就会相遇。
文章图片
下面，我们来看一下代码实现。
def detectCycle(head):
if not head:
return None
#快慢指针
slow = head
fast = head
while True:
if not fast or not fast.next:
return None
fast=fast.next.next
slow=slow.next
#相遇时，跳出循环
if fast == slow:
breakptr = head
while ptr != slow:
ptr=ptr.next
slow=slow.next
return ptr该算法的时间复杂度是O(n)，空间复杂度是O(1)。
删除链表倒数第n个节点 问题描述
LeetCode 剑指 Offer II 021. 删除链表的倒数第 n 个结点
给定一个链表，删除链表的倒数第 n个结点，并且返回链表的头结点。
示例：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
文章图片
分析问题
这个问题最简单的求解方式就是遍历一遍链表，获取到链表的长度m，然后求出倒数第n个结点的位置m-n+1，然后再遍历一次链表，找到第m-n+1的位置，删掉这个结点就好。其实，我们这里可以使用双指针法，只需要遍历一次链表就可以解决问题。
首先，我们可以设置两个指针slow和fast都指向头结点，然后让fast先走n步，之后slow和fast一起走，直到fast.next为空为止，这是slow指向的就是倒数第n+1个结点，我们通过slow.next=slow.next.next就可以把倒数第n个结点删掉。
文章图片
文章图片
文章图片
下面我们来看一下代码的实现。
def removeNthFromEnd(self,head,n):
#左右指针指向头结点
slow = fast = head
#fast先走n步
while n>0 and fast:
fast = fast.next
n=n-1if not fast:
return head.nextwhile fast.next:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return head该算法只遍历一遍链表，所以时间复杂度是O(n)，空间复杂度是O(1)。
两个链表的第一个公共结点 问题描述
LeetCode 剑指 Offer 52. 两个链表的第一个公共节点
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。
要求：空间复杂度是O(1)，时间复杂度是O(m+n)。
示例：
文章图片
分析问题
这个问题最直观的想法就是遍历链表headA，然后把headA中的所有每个节点都加入到集合中。然后再循环遍历链表headB，判断结点是否在集合中，如果在，则返回该结点，该结点就代表第一个公共结点。如果不在，继续遍历，直到结束。如果headB的所有结点都不在集合中，则表明不相交，直接返回null。
def getIntersectionNode(headA,headB):
nodes=set()
while headA:
nodes.add(headA)
headA=headA.next
while headB:
if nodes.__contains__(headB):
return headB
headB=headB.next
return None该算法的时间复杂度是O(m+n)，空间复杂度是O(n)。其中m和n分别是链表headA和headB的长度。
由于题目要求时间复杂度是O(m+n)，空间复杂度是O(1)。我们这里可以使用双指针法将空间复杂度降低到O(1)。我们分别用两个指针p1和p2分别指向headA和headB，然后同时移动指针p1和p2。当p1到达headA的末尾时，让p1指向headB，当p2到达headB的末尾时，让p2指向headA，这样，当它们相遇时，所指的节点就是第一个公共结点。
Tips:假设headA不相交的部分是a，headB不相交的部分是b，公共部分是c，那么headA的长度为a+c，headB的长度为b+c，当a等于b时，可以知道p1和p2指针同时到达第一个公共结点；当a不等于b时，在p1移动了a+b+c时，即p1走完headA，又在headB上走了b时，p2也走了a+b+c，即p2走完headB，然后又在headA上走了a，此时p1和p2正好相遇，且指向了第一个公共结点。
文章图片
def getIntersectionNode(headA,headB):
p1 = headA
p2 = headBwhile p1 != p2:
if p1:
p1=p1.next
else:
p1=headB
if p2:
p2=p2.next
else:
p2=headA
return p1两个链表生成相加链表 问题描述
LeetCode 剑指 Offer II 025. 链表中的两数相加
假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。给定两个这种链表，请生成代表两个整数相加值的结果链表。
示例：
输入：[9,3,7]，[6,3]
返回值：{1,0,0,0}
分析问题
由于两个数字相加是从个位数开始，然后再十位数、百位数。对于的链表中，我们需要将两个链表进行右端对齐，然后从右往左进行计算。
文章图片
要想让两个链表右端对齐，我们有两种实现方式。
- 将两个链表进行反转，然后直接求和。
- 借助栈这种先进后出的特性，来实现链表的右端对齐。
class Solution(object):
def reverse(self, head):
cur = head
#初始化时，pre为None
pre = None
while cur:
next=cur.next
cur.next = pre
pre = cur
cur = next
return pre
def addTwoNumbers(self, l1, l2):
#将两个链表翻转
l1 = self.reverse(l1)
l2 = self.reverse(l2)
head=ListNode(0)
pre=head
#代表是否进位
carray=0
while l1 or l2:
v1=l1.val if l1 else 0
v2=l2.val if l2 else 0
sum=v1+v2+carray
#进位数
carray=int(sum/10)
tmp=sum%10
node=ListNode(tmp)
pre.next=node
pre=pre.next
if l1:
l1=l1.next
if l2:
l2=l2.next
if carray==1:
node=ListNode(carray)
pre.next=nodereturn self.reverse(head.next)下面我们来看一下如何使用栈来求解。我们首先将两个链表从头到尾放入两个栈中，然后每次同时出栈，就可以实现链表的右端对齐相加，我们来看一下代码如何实现。
文章图片
def addTwoNumbers(l1, l2):
#申请两个栈
stack1=[]
stack2=[]
#l1入栈
while l1:
stack1.append(l1.val)
l1 = l1.next
while l2:
stack2.append(l2.val)
l2 = l2.nexthead = None
carry = 0while stack1 and stack2:
num = stack1.pop() + stack2.pop() + carry
#求进位数
carry=int(num/10)
tmp=num%10
node = ListNode(tmp)
node.next = head
head = nodes = stack1 if stack1 else stack2
while s:
num = s.pop() + carry
carry = int(num / 10)
tmp = num % 10
node = ListNode(tmp)
node.next = head
head = nodeif carry==1:
node = ListNode(carry)
node.next = head
head = node
return head单链表的排序 问题描述
LeetCode 148. 排序链表
给定一个节点数为n的无序单链表，对其按升序排序。
要求：空间复杂度 O(n)，时间复杂度 O(nlogn)。
示例：
输入：[-1,0,-2]
返回值：{-2,-1,0}
分析问题
由于题目要求时间复杂度是O(nlogn)，那时间复杂度是O(nlogn)的排序算法有归并排序、快速排序和堆排序，其中最适合链表的排序算法是归并排序。
归并排序是基于分治思想，最容易想到的就是自顶向下的递归实现。自顶向下的递归实现主要包括二个环节。
- 分割环节
- 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针法，快指针每次移动2步，慢指针每次移动1步，当快指针走到链表的末尾时，慢指针恰好指向了链表的中点位置。
- 找到中点后，将链表在中点处分割成两个子链表。
- 然后递归的进行分割，直到分割后的链表只有一个节点或者为Null。这时，分割的子链表都是有序的，因为只包含一个节点。
- 合并环节
- 将两个有序的链表合并成一个有序链表。我们可以采用双指针法求解。
- 递归执行，直到合并完成。
文章图片
class Solution:
def sortList(self, head):
#如果链表为空或者只包含一个节点，递归终止
if not head or not head.next:
return head
#使用快慢指针法来寻找链表的中点
slow=head
fast=head.next
while fast and fast.next:
fast=fast.next.next
slow=slow.next
#slow指向的就是链表的中点，将链表在中点处进行分割
head2=slow.next
slow.next=None
#递归的切割分割链表
left = self.sortList(head)
right = self.sortList(head2)
#合并链表，使用双指针法
tmp = res = ListNode(0)
while left and right:
if left.val < right.val:
tmp.next=left
left=left.next
else:
tmp.next=right
right=right.next
tmp=tmp.next
if left:
tmp.next=left
else:
tmp.next=right
return res.next该算法的时间复杂度是O(n)。由于自顶向下是通过递归来实现的，如果考虑递归调用栈的栈空间，那么该算法的空间复杂度是O(logn)。
优化
我们也可以采用自底向上的方法来求解。
首先，我们求出链表的长度length。然后将链表拆分成子链表进行合并。
- 我们用sublength表示每次需要排序的子链表的长度，初始时sublength=1。
- 每次将链表拆分成若干个长度为sublength的子链表（最后一个子链表的长度可能小于sublength），按照每两个子链表一组进行合并，合并后即可以得到若干个长度为sublength 2的有序子链表（最后一个子链表的长度可能小于sublength 2）。
- 将sublength的值加倍，重复第二步，然后对更长的有序子链表进行合并，直到有序子链表的长度大于或等于链表的长度，这样整个链表的排序就完成了。
文章图片
我们来看一下代码的实现。
class Solution:
def sortList(self, head):
#合并两个有序链表
def merge(head1, head2):
#哨兵节点
dummyHead = ListNode(0)
temp=dummyHeadwhile head1 and head2:
if head1.val <= head2.val:
temp.next = head1
head1 = head1.next
else:
temp.next = head2
head2 = head2.next
temp = temp.next
if head1:
temp.next = head1
else:
temp.next = head2return dummyHead.next#如果链表为空，直接返回
if not head:
return head
#遍历一遍链表，求出链表的长度
length = 0
node = head
while node:
length += 1
node = node.next#创建一个哨兵节点,指向链表头
dummyHead = ListNode(0)
dummyHead.next=head#初始时，子链表的长度为1
subLength = 1while subLength < length:prev=dummyHead
cur=dummyHead.nextwhile cur:
#截取长度为subLength的子链表head1
head1 = cur
for i in range(1, subLength):
if cur.next:
cur = cur.next
else:
breakhead2 = cur.next
cur.next = None#截取长度为subLength的子链表head2
cur = head2
for i in range(1, subLength):
if cur and cur.next:
cur = cur.next
else:
break#截取完后剩余的链表节点
surplus_head = None
if cur:
surplus_head = cur.next
cur.next = None
#将两个有序链表进行合并
merged = merge(head1, head2)
#将排好序的链表插入到新生成的链表里
prev.next = merged#将指针移动到链表的末尾
while prev.next:
prev = prev.next#继续合并剩余的节点
cur=surplus_head
subLength = subLength * 2return dummyHead.next该算法的时间复杂度是O(nlogn)，空间复杂度是O(1)。
判断一个链表是否为回文结构 问题描述
LeetCode 剑指 Offer II 027. 回文链表
给定一个链表，请判断该链表是否为回文结构。回文是指该字符串正序逆序完全一致。
示例：
输入：{1,2,2,1}
输出：true
说明：1 -> 2 -> 2 -> 1
分析问题
回文串是指正读反读都一样的字符串，最简单的是使用双指针法。但是对于链表这种数据结构来说，指针只能向一个方向移动，也就是说只能找到后继节点，没办法找到前驱节点。所以没办法使用双指针法，要想使用双指针，我们就需要把链表元素放入一个数组中，然后再去判断是否是回文，这需要O（n）的空间复杂度，这里就不在赘述。大家可以去看第44题。
我们可以这么考虑，将链表的后半部分进行反转，然后将前半部分和后半部分进行比较，如果相同就代表是回文链表，否则不是回文链表。寻找链表的中点我们可以使用快慢指针的方式。
- 快慢指针寻找链表中点。
文章图片
- 对链表的后半部分进行翻转
文章图片
- 前半部分和后半部分进行比较。
文章图片
class Solution:
def isPalindrome(self, head) -> bool:
#链表为空，直接返回true
if head is None:
return True#找到链表的中点
middle_point = self.middle_point(head)
second_start = self.reverse_list(middle_point.next)#判断前半部分和后半部分是否相等
result = True
first = head
second = second_start
while result and second is not None:
if first.val != second.val:
result = False
first = first.next
second = second.next#还原链表并返回结果
middle_point.next = self.reverse_list(second_start)
return result#快慢指针寻找中点
def middle_point(self, head):
fast = head
slow = head
while fast.next is not None and fast.next.next is not None:
fast = fast.next.next
slow = slow.next
return slow#翻转链表
def reverse_list(self, head):
previous = None
current = head
while current is not None:
next_node = current.next
current.next = previous
previous = current
current = next_node
return previous链表内指定区间反转 问题描述
LeetCode 92. 反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表 。
示例：
输入：head = [1,2,3,4,5]， left = 2，right = 4
输出：[1,4,3,2,5]
文章图片
分析问题
对于链表相关的题目，我们一定要先想清楚思路，搞懂指针移动的先后顺序。
对于这道题，我们可以采用头插法来求解。在链表反转的区间内，当我们每次遍历到一个节点时，就让该节点插入到反转部分的起始位置。如下图所示：
文章图片
具体来说，我们定义三个指针pre、cur、next变量。
- 我们首先将pre移动到第一个要反转的节点的前面，即pre->next=left
- 然后将指针cur移动到第一个要反转的节点位置上，即cur=left，
- 然后将 cur->next 赋值给变量next。
- 将cur的下一个节点指向next的下一个节点，即cur->next=next->next
- 然后将next的下一个节点指向pre的下一个节点，即next->next=pre->next
- 然后将next插入到链表头部，即pre->next=next。
- 然后循环往复执行3、4、5、6，直到反转完链表区间内的节点。
文章图片
下面我们来看一下代码如何实现。
class Solution:
def reverseBetween(self, head, left, right):
#设置哨兵节点，对于链表相关的问题，我们通过设置哨兵节点
#可以省去边界条件的判断
dummynode = ListNode(-1)
#哨兵节点指向链表头
dummynode.next = head
pre = dummynode
#遍历，使得pre指向链表反转部分
#的第一个结点left
for _ in range(left - 1):
pre = pre.next
#cur指向链表反转部分的第一个节点
cur = pre.next
for _ in range(right - left):
next = cur.next
cur.next = next.next
next.next = pre.next
pre.next = next
return dummynode.next该算法的时间复杂度是O(N)，其中 N 是链表总节点数。最多只遍历了链表一次，就完成了反转。空间复杂度是O(1)，只用到了常数个变量。
删除有序链表中重复的元素-I 问题描述
LeetCode 83. 删除排序链表中的重复元素
删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次。
示例：
输入：{1,1,2}
输出：{1,2}
分析问题
因为给定的链表是排好序的，所以我们可以知道重复的元素在链表中出现的位置一定是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。
开始时，我们定义一个指针cur指向链表的头结点，然后开始对链表进行遍历。如果cur.val==cur.next.val时，我们就将cur.next这个节点从链表中移除；如果不相同，我们将指针cur后移，即cur=cur.next。当遍历完整个链表之后，我们返回链表的头结点即可。
文章图片
下面我们来看一下代码的实现。
class Solution:
def deleteDuplicates(self, head):
#如果链表为空，直接返回
if not head:
return head
#cur指向头结点
cur = head
#当cur.next不为空时
while cur.next:
#如果值相同，删除cur.next节点
if cur.val == cur.next.val:
cur.next = cur.next.next
#否则cur后移
else:
cur = cur.next
return head该算法的时间复杂度是O(N)，空间复杂度是O(1)。
删除有序链表中重复的元素-II 问题描述
LeetCode 82. 删除排序链表中的重复元素 II
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。返回同样按升序排列的结果链表。
示例:
输入：head = [1，2，3，3，4，5]
输出：[1，2，5]
文章图片
分析问题
由于给定的链表是有序的，所以链表中重复的元素在位置上肯定是相邻的。因此，我们可以对链表进行一次遍历，就可以删除重复的元素。
这里需要注意一点，由于可能会删除头结点head，我们引入了一个哨兵节点dummy，让dummy.next=head，这样即使head被删除了，那么也会操作dummy.next指向新的链表头结点，所以最终返回dummy.next即可。
首先，我们让cur指针指向链表的哨兵节点，然后开始对链表进行遍历。如果cur.next与cur.next.next对应的元素值相同，那么我们就需要将cur.next以及后面所有值相同的链表节点全部删除，直到cur.next为空节点或者其元素值与其不同。如果cur.next与cur.next.next对应的元素值不相同，那么我们就可以将cur 指向 cur.next。
文章图片
文章图片
下面我们来看一下代码的实现。
class Solution:
def deleteDuplicates(self, head):
#如果链表为空，直接返回
if not head:
return head
#创建一个哨兵节点
dummy = ListNode(0)
dummy.next=head#开始时，将cur指向哨兵节点
cur = dummy
while cur.next and cur.next.next:
#如果cur.next.val和cur.next.next.val相同，删除重复元素
if cur.next.val == cur.next.next.val:
data = cur.next.val
while cur.next and cur.next.val == data:
cur.next = cur.next.next
else:
cur = cur.nextreturn dummy.next该算法的时间复杂度是O(n)，空间复杂度是O(1)。
链表的奇偶重排 问题描述
LeetCode 328. 奇偶链表
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
示例：
输入：{1，2，3，4，5，6}
输出：{1，3，5，2，4，6}
分析问题
要想把一个链表的奇数节点和偶数节点分别排在一起，我们可以先分离链表，把一个链表拆分成两个链表，其中一个是奇数链表，另一个是偶数链表，最后将偶数链表拼接在奇数链表后即可。
我们都知道，对于一个链表来说，相邻节点的奇偶性是不同的。原始链表的头节点head是奇数链表的头节点，head的后一个节点是偶数链表的头节点，我们假设是evenHead ，则evenHead = head.next。我们维护两个指针odd和even分别指向奇数链表和偶数链表的最后一个节点，初始时 odd=head，even=evenHead。通过不断的更新odd和even，将链表分割成奇数链表和偶数链表。
- 更新奇数节点，我们令 odd.next=even.next，此时奇数链表的最后一个节点指向了偶数节点even的后一个节点。然后令odd=odd.next，此时odd变成了even的后一个节点。
- 更新偶数节点，我们令 even.next=odd.next，此时偶数节点的最后一个节点指向了奇数节点odd的后一个节点。然后令even=even.next，此时even变成了odd的后一个节点。
文章图片
文章图片
文章图片
下面我们来看一下代码的实现。
class Solution:
def oddEvenList(self, head):
#如果链表为空，直接返回
if not head:
return head
#evenHead指向偶数链表的头节点
evenHead = head.next
#指向奇数链表和偶数链表的末尾节点
odd = head
even = evenHead
while even and even.next:
#奇数链表的末尾节点指向偶数节点的下一个节点
odd.next = even.next
#奇数链表末尾节点后移
odd = odd.next
#偶数链表的末尾节点指向奇数节点的下一个节点
even.next = odd.next
#偶数链表末尾节点后移
even = even.next#偶数链表连接到奇数链表的末尾
odd.next = evenHead
return head该算法的时间复杂度是O(n)，空间复杂度是O(1)。
重排链表 问题描述
LeetCode 143. 重排链表
给定一个单链表 L 的头节点head ，单链表 L 表示为：L0 -> L1 -> ... -> Ln-1 -> Ln，将其重新排列后变成 L0 -> Ln -> L1 -> Ln-1 -> ...。不能只是单纯的改变节点的值，而需要实际的进行节点的交换。
示例：
输入： head = [1，2，3，4]
输出： [1，4，2，3]
分析问题
首先，我们来观察一下链表重置前和重置后的变化。如下图所示：
文章图片
我们可以知道，重置后的链表是将原链表的左半端和反转后的右半段进行节点交叉合并而成的，所有我们可以分三步来求解。
- 找到原链表的中点，将链表分割成左右两部分。
- 对后半部分进行反转。
- 建原链表的左半部分和反转后的右半部分进行合并。
class Solution:
def reorderList(self, head):
#如果链表为空，直接返回
if not head:
return
#寻找链表的中点，将链表分割成左右两部分
mid = self.middleNode(head)
left = head
right = mid.next
mid.next = None
#对右半部分的链表进行反转
right = self.reverseList(right)
#左右链表进行合并
self.mergeList(left, right)def middleNode(self, head):
#使用快慢指针法求中点
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow#对链表进行反转
def reverseList(self, head):
prev = None
curr = head
while curr:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
return prev#对两个链表进行合并操作
def mergeList(self, l1, l2):
#l1和l2的节点数量相差不会超过一个
#所以直接合并就好
while l1 and l2:
tmp1 = l1.next
tmp2 = l2.nextl1.next = l2
l1 = tmp1l2.next = l1
l2 = tmp2该算法的时间复杂度是O(N)，空间复杂度是O(1)。
链表中倒数最后k个节点 问题描述
LeetCode 剑指 Offer 22. 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
输入：{1,2,3,4,5}，2
输出：{4,5}
分析问题
这道题比较简单，我们可以直接使用快慢指针来求解，开始时申请两个指针同时指向链表的头结点，记为slow和fast，然后让fast先移动k步，再然后让两个指针slow和fast同时移动，使得fast和slow在移动的过程中总是相隔k个单位，当fast指针走到末尾的时候，此时slow正好指向的是倒数第k个位置。
文章图片
下面我们来看一下代码的实现。
class Solution:
def FindKthToTail(self, pHead, k):
#快慢指针同时执行头结点
slow=fast=pHead
#快指针移动k步
for i in range(0,k):
#如果还没走完k步就走到了链表尾，直接返回None
if not fast:
‘return None
fast = fast.next
#两个指针同时移动,直到fast为空
while fast:
slow=slow.next
fast=fast.nextreturn slow划分链表 问题描述
LeetCode 面试题 02.04. 分割链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。并且两个部分之内的节点之间与原来的链表要保持相对顺序不变。
示例：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
分析问题
简单来说，我们只需要维护两个链表small和large即可，使得small链表按顺序存储所有小于x的节点，large链表按顺序存储所有大于等于x的节点。当我们遍历完链表之后，只需要将small链表的尾节点指向large链表的头结点即可完成分割链表的操作。
首先，我们创建两个节点smallHead和largeHead分别为两个链表的哑结点，这是为了方便的处理头结点为空的边界条件，同时smallTail和largeTail分别指向两个链表的末尾节点。开始时，smallHead=smallTail，largeHead=largeTail，然后从前往后遍历链表head，判断当前节点的值是否小于x，如果小于x，就将smallTail的next指针指向该节点，否则将largeTail的next指针指向该节点。
遍历结束后，我们将largeTail的next指针置为空，这是因为当前节点复用的是原链表的节点，而其 next 指针可能指向一个小于 x的节点，我们需要切断这个引用。然后将smallTail的next指针指向largeHead的next指针指向的节点，来将两个链表合并起来，最后返回smallHead.next即可。
文章图片
文章图片
文章图片
文章图片
下面我们来看一下代码实现。
class Solution(object):
def partition(self, head, x):
#创建两个哑结点
smallHead = smallTail = ListNode(0)
largeHead = largeTail = ListNode(0)
#遍历链表
while head:
#如果head.val【面试高频算法题之链表】该算法的时间复杂度是O(n)，空间复杂度是O(1)。
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- 2018国考外交部面试演讲不再难——只需把握好三点
- iOS面试题--基础
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列