共计 19567 个字符，预计需要花费 49 分钟才能阅读完成。
链表
全文概览
如果须要本文的 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 = next
class Solution:
def reverse(self, head):
cur = head
#初始化时，pre 为 None
pre = None
while cur:
next=cur.next
cur.next = pre
pre = cur
cur = next
return pre
head=ListNode(1,None)
cur=head
for i in range(2,6):
tmp=ListNode(i,None)
cur.next=tmp
cur=cur.next
s=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=l2
return head.next其实，咱们这里也能够应用递归的形式来实现。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, l1, l2):
#链表 l1 为空，不须要合并，间接返回 l2
if(l1==None):
return l2
#同理，l2 为空，间接返回 l1 即可
if(l2==None):
return l1
if(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
| | | |
7 13 18 28
| | |
8 21 37
|
20
实现函数 flatten()，该函数用来将链表扁平化成单个链表。例如下面的链表，输入链表为
4 -> 7 -> 8 -> 9 -> 13 -> 15 -> 18 ->19 -> 20 -> 21 -> 28 -> 37 题目要求咱们把二维有序链表合并成一个单链表，咱们来把问题简化一下，假如主链表只有两个节点，即这个二维链表变成如下所示。
4 -> 9
| |
7 13 旋转一下 4 -> 7 -> 8 -> 20
| ----------> |
8 9 -> 13
|
20 这不就是咱们下面讲的两个有序链表合并吗？那如果主链表有多个节点呢？咱们能够应用归并的思维，一一去合并就好了，如下图所示。
上面咱们来看一下代码如何实现。
class ListNode:
def __init__(self, val=0, right=None, down=None):
self.val = val
self.right = right
self.down = down
class Solution:
def mergeTwoLists(self, l1, l2):
#如果有一个链表为空，则合并后的链表就是另外一个
if(l1==None):
return l2
if(l2==None):
return l1
if(l1.val<=l2.val):
l1.down=self.mergeTwoLists(l1.down,l2)
return l1
else:
l2.down=self.mergeTwoLists(l1,l2.down)
return l2
def 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 = next
class 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, head
def reverseKGroup(self, head, k):
#初始化一个哨兵节点，防止临界条件简单的判断
prehead = ListNode(0)
#哨兵节点指向头结点
prehead.next = head
pre = prehead
while 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.next
return 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 = True
while slow != fast || start:
start=False
if not fast or not fast.next:
return False
slow = slow.next
fast = fast.next.next
return 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:
break
ptr = 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-1
if not fast:
return head.next
while 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 = headB
while 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=node
return 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.next
head = None
carry = 0
while stack1 and stack2:
num = stack1.pop() + stack2.pop() + carry
#求进位数
carry=int(num/10)
tmp=num%10
node = ListNode(tmp)
node.next = head
head = node
s = 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 = node
if 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=dummyHead
while 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 = head2
return 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 = 1
while subLength < length:
prev=dummyHead
cur=dummyHead.next
while cur:
#截取长度为 subLength 的子链表 head1
head1 = cur
for i in range(1, subLength):
if cur.next:
cur = cur.next
else:
break
head2 = 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 * 2
return 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.next
return 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 的后一个节点。
通过以上两步，咱们就实现了对一个奇数节点和一个偶数节点的拆散。反复上述操作，直到全副节点拆散实现。最初令 odd.next = evenHead，将偶数链表连贯在奇数链表之后，即实现了奇数链表和偶数链表的合并。
上面咱们来看一下代码的实现。
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.next
l1.next = l2
l1 = tmp1
l2.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.next
return 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<x, 将以后节点插入 small 中，否则插入 large 中
if head.val < x:
smallTail.next=head
smallTail=smallTail.next
else:
largeTail.next=head
largeTail=largeTail.next
head=head.next
largeTail.next=None
#合并两个链表
smallTail.next=largeHead.next
return smallHead.next该算法的工夫复杂度是 O(n)，空间复杂度是 O(1)。