时间复杂度是
归并排序基于分治算法。最容易想到的实现方式是自顶向下的递归实现，考虑到递归调用的栈空间，自顶向下归并排序的空间复杂度是
如果使用指针法，需要在循环之前初始化指针的指向；特别注意：循环开始后，全部的操作都是围绕指针的，不能再操作节点了
链表的插入：需要初始化一个伪头节点（防止被插入节点的位置是0），被插入的节点应该和前后节点进行连接
链表的反转：
- 可以边走边反转，也就是直接反转整个链表，一定要初始化一个空，作为反转后链表最后一个节点指向的对象
- 遍历到一定个数的子链表再进行反转，因为插回去时需要前后两个节点进行连接，所以要标记出待反转子链表的头和尾；不要忘记初始化空，用以反转后子链表最后一个节点指向的对象
- 两个指针，一个指向前一个节点（因为需要链表删除操作，所以需要知道当前节点的上一个节点），一个指向当前节点
- 如果当前节点的值等于目标值，删除操作完成后，需要移动当前指针
- 如果当前节点的值不等于目标值，则两个指针都需要移动
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
# 初始化哨兵节点
sentinel = ListNode(0)
sentinel.next = head
# 初始化两个指针，分别指向前一个节点和当前节点
prev, curr = sentinel, head
while curr:
# 当前指针不为空
if curr.val == val:
# 令当前节点的指针，等于前一个节点指针
prev.next = curr.next
else:
# prev 向后移
prev = curr
# curr 向后移
curr = curr.next
# 返回 头节点
return sentinel.next-
这里的函数调用方法是一次调用的，首先一定会实例化 MyLinkedList，然后再使用这个类下的各种函数
-
size 应该是会根据每次调用时进行已有链表的长度计算
-
单链表复杂度分析
- 时间复杂度：
addAtHead： O(1)addAtIndex，get，deleteAtIndex: O(k)，其中 k 指的是元素的索引。addAtTail：O(N)，其中 N 指的是链表的元素个数。 - 空间复杂度：所有的操作都是 O(1)
- 时间复杂度：
# 单链表方法
class ListNode:
def __init__(self, x):
# 自定义新节点，指定节点的值，指针为空
self.val = x
self.next = None
class MyLinkedList:
def __init__(self):
# 初始化哨兵节点
self.size = 0 # 始终存在一个伪头，所以这里的size=0
self.head = ListNode(0) # sentinel node as pseudo-head
def get(self, index: int) -> int:
"""
Get the value of the index-th node in the linked list. If the index is invalid, return -1.
"""
# if index is invalid
if index < 0 or index >= self.size:
return -1
# 指定头节点
curr = self.head
# index steps needed
# to move from sentinel node to wanted index
for _ in range(index + 1):
curr = curr.next
return curr.val # 返回这个节点的值
def addAtHead(self, val: int) -> None:
"""
Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
"""
self.addAtIndex(0, val) # 直接调用 addAtIndex
def addAtTail(self, val: int) -> None:
"""
Append a node of value val to the last element of the linked list.
"""
self.addAtIndex(self.size, val) # 直接调用 addAtIndex，新添加的节点index=self.size
def addAtIndex(self, index: int, val: int) -> None:
"""
Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
"""
# If index is greater than the length,
# the node will not be inserted.
if index > self.size:
return
# [so weird] If index is negative,
# the node will be inserted at the head of the list.
if index < 0:
index = 0
# 或许也可以理解为 要新增一个节点，这时其列表长度+1
# 记录size变化的目的是为了比较index与size的大小，所以不能省略
self.size += 1
# find predecessor of the node to be added
pred = self.head
for _ in range(index):
pred = pred.next
# node to be added（生成新的节点）
to_add = ListNode(val)
# 进行插入操作
to_add.next = pred.next
pred.next = to_add
def deleteAtIndex(self, index: int) -> None:
"""
Delete the index-th node in the linked list, if the index is valid.
"""
# if the index is invalid, do nothing
if index < 0 or index >= self.size:
return
# 要删除一个节点，其列表长度-1
self.size -= 1
# find predecessor of the node to be deleted
pred = self.head
for _ in range(index):
pred = pred.next
# delete pred.next
pred.next = pred.next.next- 注意：比较从哪头开始比较近的时候，
- 使用
get方法时，判断条件比较的是index-1和size-index - 使用添加和删除方法时，判断条件比较的是
index和size-index
- 使用
- 具体循环过程中走几步：
get：把伪头和伪尾算进去了，因此从头遍历：index+1，从尾遍历：size-indexaddAtIndex：插入第index个节点之前，因此从头遍历：index，从尾遍历：size-indexdeleteAtIndex： 删去的节点总是即将访问，但是还么访问的那个节点；从头遍历结束时cur的下一个节点，从尾遍历时cur_n的上一个节点，正好就将下一个遍历的对象节点删去；因此从头遍历：index，从尾遍历：size-1-index
- 双链表方法复杂度分析：
- 时间复杂度
addAtHead，addAtTail： O(1)get，addAtIndex，delete：O(min(k, N−k))，其中 k 指的是元素的索引。
- 空间复杂度：
- 所有的操作都是 O(1)
- 时间复杂度
# 双链表方法
class ListNode:
def __init__(self, x):
self.val = x
self.next, self.prev = None, None # 每个节点有两个指针
class MyLinkedList:
def __init__(self):
self.size = 0
# sentinel nodes as pseudo-head and pseudo-tail，伪头，伪尾节点互相连接
self.head, self.tail = ListNode(0), ListNode(0)
self.head.next = self.tail
self.tail.prev = self.head
def get(self, index: int) -> int:
"""
Get the value of the index-th node in the linked list. If the index is invalid, return -1.
"""
# if index is invalid
if index < 0 or index >= self.size:
return -1
# choose the fastest way: to move from the head
# or to move from the tail
if 1 + index < self.size - index:
curr = self.head
for _ in range(index + 1): # 注意这里+1
curr = curr.next
else:
curr = self.tail
for _ in range(self.size - index):
curr = curr.prev
return curr.val
def addAtHead(self, val: int) -> None:
"""
Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
"""
# 相比于单链表，这里选择直接操作伪头，以及伪头的下一个
# 将新节点插入到他们之间
pred, succ = self.head, self.head.next
self.size += 1 # 别忘了这里size要+1
to_add = ListNode(val)
to_add.prev = pred
to_add.next = succ
pred.next = to_add
succ.prev = to_add
def addAtTail(self, val: int) -> None:
"""
Append a node of value val to the last element of the linked list.
"""
# 相比于单链表，这里选择直接操作伪尾，以及伪尾的上一个
# 将新节点插入到他们之间
succ, pred = self.tail, self.tail.prev
self.size += 1
to_add = ListNode(val)
to_add.prev = pred
to_add.next = succ
pred.next = to_add
succ.prev = to_add
def addAtIndex(self, index: int, val: int) -> None:
"""
Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
"""
# If index is greater than the length,
# the node will not be inserted.
if index > self.size:
return
# [so weird] If index is negative,
# the node will be inserted at the head of the list.
if index < 0: # 注意：这里不要使用类中的别的函数
index = 0
# find predecessor and successor of the node to be added
# 依旧判断从哪个方向加更快
if index < self.size - index:
# 注意：这里区别于 get 方法，是在第index个节点之前进行添加节点
# 所以这里的 index 不用 +1 去比
pred = self.head
for _ in range(index):
pred = pred.next
succ = pred.next
else:
succ = self.tail
for _ in range(self.size - index):
succ = succ.prev
pred = succ.prev
# insertion itself
self.size += 1
to_add = ListNode(val)
to_add.prev = pred
to_add.next = succ
pred.next = to_add
succ.prev = to_add
def deleteAtIndex(self, index: int) -> None:
"""
Delete the index-th node in the linked list, if the index is valid.
"""
# if the index is invalid, do nothing
if index < 0 or index >= self.size:
return
# find predecessor and successor of the node to be deleted
# 还是判断从哪里开始
if index < self.size - index:
pred = self.head
for _ in range(index):
pred = pred.next
succ = pred.next.next
else:
succ = self.tail
for _ in range(self.size - 1- index): # 注意这里的-1
succ = succ.prev
pred = succ.prev.prev
# delete pred.next
self.size -= 1
pred.next = succ
succ.prev = pred- 迭代法
- 难点：注意需要在头节点前定义一个空头，pre = None
- 复杂度分析
- 遍历一次链表，时间复杂度为
O(n) - 三个指针，空间复杂度为
O(1)
- 遍历一次链表，时间复杂度为
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# 首先定义一个指针，指向头节点
# 这里不存在头节点的前面添加节点，所有不需要定义伪头
cur = head
pre = None # 别忘了在头节点前定义一个空头
while (cur != None):
tmp = cur.next # 当前节点的下一节点赋给tmp
cur.next = pre # 当前节点连接到上一个更新好的节点
pre = cur # 移动pre指针到新连接好的节点上
cur = tmp # 移动cur指针到待处理的下一个节点上
return pre # 当 cur 指向 None 时，pre指针已经指向了反转后链表的头节点处- 递归法
- 复杂度分析
- 链表仅被遍历一遍，时间复杂度为
O(n) - 一共递归n次，需要数量为n的栈空间，空间复杂度为
O(n)
- 链表仅被遍历一遍，时间复杂度为
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# 当前函数的作用是：翻转当前链表，返回新的头指针
# 递归反转head-next后的链表
# 此时head.next就是反转后的尾部
# 将head添加到尾部之后，即head.next.next = head
# 并将head.next置为None
if not head or not head.next: # 遇到 none 停止迭代
return head
p = self.reverseList(head.next) # p 是 head.next的下一个节点，即 head.next.next = p
head.next.next = head # 完成反转 即 3 -> 4 转为 4 -> 3
head.next = None # 即 4 -> 3 -> none
return p # p 是从后往前的每一个节点92，反转链表2，中等
核心方法：建立哨兵节点，首先找到待反转起点的前一个节点，也就是left的前一个，然后从left节点开始，依次向后走 right - left 步，每步分成如下四个步骤：
- 断开当前节点与下一个节点，下一个节点为tmp
- 将当前节点指向下一个节点的下一个节点
- 将下一个节点指向前一个节点的下一个节点
- 将一个节点指向下一个节点
如果还是不明白，可以画一个图解释一下
- 时间复杂度：O(n)，链表节点数
- 空间复杂度：O(1)，常数空间
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
dummy = ListNode(-1)
dummy.next = head
pre = dummy
for _ in range(left - 1):
# 因为这里的left-1是要反转的第一个位置，所以不能取到
pre = pre.next
# 当前pre指向的是left的前一个节点
# cur 为待反转的第一个节点
cur = pre.next
for _ in range(right - left):
tmp = cur.next
cur.next = tmp.next
tmp.next = pre.next
pre.next = tmp
return dummy.next- 双指针，fast一次走两点，slow一次走一点，当fast和slow相遇时即为相遇点
- 然后设置fast一次走一点，另设置一个指针从头节点处一次走一点，当二者相遇时即为环的入口
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
fast = head
slow = head
while True:
# 如果没有环，那么fast或是fast.next就为空，直接返回
if not (fast and fast.next): return
fast, slow = fast.next.next, slow.next
if slow == fast: break # 一旦二者相等，则退出循环
fast = head
while (slow != fast):
slow = slow.next
fast = fast.next
return fast- 分析复杂度：
- 时间复杂度：O(m+n)
- 空间复杂度：O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1, l2):
# 定义伪头节点，并指定当前指针从头节点开始
prehead = ListNode(-1) # 这个节点的值其实是随机指定的
prev = prehead
# 只要l1和l2不为空，就把小的那个作为伪头的下一个，且自身链表后移一位
while l1 and l2:
if l1.val <= l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
prev = prev.next
# 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
prev.next = l1 if l1 is not None else l2
return prehead.next- 复杂度分析：
- 空间复杂度：O(m+n)
- 时间复杂度：O(m+n)
- 逻辑如下
class Solution:
def mergeTwoLists(self, l1, l2):
# 遇到空链表，则返回另一个链表
if l1 is None:
return l2
elif l2 is None:
return l1
# 我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。
# 实际的递归过程是由大到小返回节点
elif l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
- 复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
# 使用线性表
if not head: return
# 将所有节点一次加入列表中
nodes = list()
node = head
while(node):
nodes.append(node)
node = node.next
# 初始化指针位置
i, j = 0, len(nodes)-1
while (i < j):
nodes[i].next = nodes[j]
i += 1
# 这一步加在这里是为了至少要完成一次相加
if i == j: break
nodes[j].next = nodes[i]
j -= 1
# 最后一个节点的指针要指向空
nodes[i].next = None- 首先查找链表的中心位置（快慢指针）
- 对中心位置的后半部分进行反转链表（迭代法）
- 合并链表：这里相当于每次从l2中取一个插入l1，然后再移动l1和l2指针，插入下一个
- 复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if not head: return
mid = self.findMid(head)
# 拆分为两个新的链表
l1 = head
l2 = mid.next
mid.next = None # 注意：这一步不能忘，有了这一步才能将链表分隔开
l2_r = self.reverseListNode(l2)
self.merge(l1, l2_r)
def findMid(self, head):
"""找到链表的中心节点，快慢指针法"""
fast = head
slow = head
while (fast and fast.next):
fast = fast.next.next
slow = slow.next
return slow
def reverseListNode(self, head):
"""迭代法，反转链表"""
cur = head
pre = None
while (cur):
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
def merge(self, l1, l2):
"""链表合并"""
while(l1 and l2):
l1_tmp = l1.next
l2_tmp = l2.next
# 注意：节点指针完成重新指向后，再移动指针
l1.next = l2
l1 = l1_tmp
# 这里相当于每次从l2中取一个插入l1，然后再移动l1和l2指针，插入下一个
l2.next = l1
l2 = l2_tmp- 如果要删除某一节点，必须确定上一个节点，所以要在代码中加入上一个节点的指针
- 如果链表长度就等于1，且n=1，那么就回删除第一个，所以这里需要加入伪头节点指向head
- 这样的话，可以一开始就指定【上一节点】的初始值为伪头，在slow，fast同时行走时再令【上一节点】等于slow节点
- 复杂度分析：
- 时间复杂度：O(链表长度)
- 空间复杂度：O(1)
- 当然，slow也可以从伪头开始，fast走到头时，slow.next 才是需要删除的节点，可直接令 slow.next = slow.next.next
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
# 因为有可能要把第一个删掉，所以需要添加一个伪头
sental = ListNode(-1)
sental.next = head
fast = head
slow = head
while (n > 0):
fast = fast.next
n -= 1
# 删除节点需要被删除节点的前一个节点
prev = sental
while (fast != None):
fast = fast.next
prev = slow
slow = slow.next
tmp = slow.next
prev.next = tmp
return sental.next- 复杂度分析：
- 时间复杂度：O(nlogn)
- 空间复杂度：O(logn)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间。
class Solution:
def sortList(self, head: ListNode) -> ListNode:
def sortFunc(head: ListNode, tail: ListNode) -> ListNode:
if not head: return head # 链表为空，直接返回这个链表
# 这里要判断是否到了二分链表的尾部，如果到达，则将最后一个节点指向none，表示断开或完结
if head.next == tail:
head.next = None
return head
# 使用快慢指针，fast比slow快一步
slow = fast = head
while fast != tail:
slow = slow.next
fast = fast.next
# 这里要确保fast不能指向空
if fast != tail:
fast = fast.next
mid = slow
return merge(sortFunc(head, mid), sortFunc(mid, tail))
def merge(head1: ListNode, head2: ListNode) -> ListNode:
dummyHead = ListNode(0) # 设置伪头
temp, temp1, temp2 = dummyHead, head1, head2
while temp1 and temp2:
# 谁小，就连接谁，谁的指针就后移一位
if temp1.val <= temp2.val:
temp.next = temp1
temp1 = temp1.next
else:
temp.next = temp2
temp2 = temp2.next
# 当前的temp已经更新了，需要后移一位
temp = temp.next
# 把剩余的那个链表接在temp后面
if temp1:
temp.next = temp1
elif temp2:
temp.next = temp2
return dummyHead.next
return sortFunc(head, None)难点：将链表划分为多个长度为subLength的字链表，对每个长度为 subLength 的子链表进行合并排序，然后成倍增加subLength的长度；具体的合并有序链表可以使用【合并两个有序链表】的方法
- 复杂度分析：
- 时间复杂度：O(nlogn)，其中 nn 是链表的长度。
- 空间复杂度：O(1)
class Solution:
def sortList(self, head: ListNode) -> ListNode:
def merge(head1: ListNode, head2: ListNode) -> ListNode:
"""合并两个有序链表"""
dummyHead = ListNode(0)
temp, temp1, temp2 = dummyHead, head1, head2
while temp1 and temp2:
if temp1.val <= temp2.val:
temp.next = temp1
temp1 = temp1.next
else:
temp.next = temp2
temp2 = temp2.next
temp = temp.next
if temp1:
temp.next = temp1
elif temp2:
temp.next = temp2
return dummyHead.next
if not head:
return head
# 首先确定链表长度，使用length存储
length = 0
node = head
while node:
length += 1
node = node.next
# 设定伪头，初始化每次排序的子链表长度为1
dummyHead = ListNode(0, head)
subLength = 1
while subLength < length: # 子长度小于总长度时
# 分别指向伪头节点，和头节点
prev, curr = dummyHead, dummyHead.next
while curr:
# 重点：这个循环保证了每个长度为subLength的子链表都是有序的
# 如果当前节点不为空，另当前节点为head1
head1 = curr
# 在固定 subLength 的条件下，遍历子链表，移动当前节点
for i in range(1, subLength):
if curr.next:
curr = curr.next
else:
break
# 将当前节点后面的链表赋值给head2
head2 = curr.next
# 将子链表取出
curr.next = None
# 将当前节点指向剩余链表的头节点
curr = head2
for i in range(1, subLength):
if curr and curr.next:
curr = curr.next
else:
break
# 再获取一个子链表
succ = None
if curr:
succ = curr.next # succ指向剩余链表
curr.next = None
# 合并两个链表，对其排序
merged = merge(head1, head2)
# 上一节点连接排序好的节点
prev.next = merged
# 将上一节点的指针指向排序节点的末尾
while prev.next:
prev = prev.next
curr = succ # curr指向剩余链表
# subLength加倍，按位运算：下面的表达式等价于subLength *= 2
# 由于每个长度为subLength为子链表都是有序的，更新subLength时才能成倍的增加
subLength <<= 1
return dummyHead.next-
边走边反转，需要预先设定反转链表的尾节点prev=None
-
快慢指针移动时，fast.next != None 也需要作为判断条件，这样可以不对长度为1的原始链表做任何处理
-
链表长度是奇数的情况下，slow还需要向前走一步，这样将中间位置隔开，不属于前后任意链表
-
上述操作中还需要加入 slow.next != None 的情况，这样就能划分出链表长度等于2的特例，是的prev指向第一个节点，而slow指向第二个节点
-
使用 prev 作为判断条件是为了将链表长度为1的情况直接返回True。因为链表长度为1时，由于 fast.next != None 的条件，prev不会赋值，还是None，这样就可以直接得到True
-
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
# 首先通过快慢指针找到链表的中点，然后分为两个链表，将其中一个链表进行反转
if not head: return False
fast = head
slow = head
prev = None # 设置空节点的目的是作为反转链表的最后一个节点指向的那个节点
while fast and fast.next:
fast = fast.next.next
tmp = slow.next
# 开始反转
slow.next = prev
prev = slow # 移动指针，指向反转后新链表的头节点
slow = tmp
# 前半部链表已经反转完成，需要判断链表长度是否为奇数
# 如果是奇数，则slow再向前走一步
if fast and slow.next:
# 这里判断slow.next，是为了保证链表长度为2时，slow.next为空，不需要让slow往后走
# 也就是说，prev 和 slow 分别指向了两个长度相等的链表，可以直接开始比较了
slow = slow.next
# 此时两个链表分别的头节点是prev和slow
# 所以两个头节点边走边比，有一个不相等就返回False，否则返回True
# 使用 prev 作为判断条件是为了将链表长度为1的情况直接返回True
# 因为链表长度为1时，prev不会赋值，还是None
while prev:
if prev.val != slow.val:
return False
prev = prev.next
slow = slow.next
return True- 需要判断一组的长度大于或等于k，才能进行反转，而不是一指针一边走一边反转
- 反转链表后，新反转的链表的头部需要与上一个子链表的尾部连接，尾部需要与下一个子链表的头部进行连接
- 复杂度分析：
- 时间复杂度：O(n)，其中 n 为链表的长度。head 指针会在
$O(\lfloor \frac{n}{k} \rfloor)$ 个节点上停留，每次停留需要进行一次 O(k) 的翻转操作。 - 空间复杂度：我们只需要建立常数个变量。
- 时间复杂度：O(n)，其中 n 为链表的长度。head 指针会在
class Solution:
# 翻转一个子链表，并且返回新的头与尾
def reverse(self, head: ListNode, tail: ListNode):
"""
prev：相当于链表从后往前遍历时的指针，直到prev指向原始子链表的tail，在遍历中指向处理节点的前一个节点
nex：指向未处理节点
p：指向当前需要处理的节点
"""
prev = tail.next
p = head
# 直到 prev 按顺序遍历到最后一个节点，也就是当前处理的节点已经将所有节点都处理了
while prev != tail:
nex = p.next
p.next = prev
prev = p
p = nex
return tail, head # 头尾互换
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
hair = ListNode(0) # 在链表之前添加伪头节点
hair.next = head # 将伪头节点指向头节点
pre = hair # pre 表示上一个节点，这样做有益于插入反转后的子链表时能够与前面的链表进行连接
while head: # 当头节点不为空
tail = pre # 首先将 tail指针 指向 pre
# 查看剩余部分长度是否大于等于 k
for i in range(k):
tail = tail.next
# 以下条件对应着当剩余子链表长度不够k了，就直接返回
if not tail:
return hair.next
nex = tail.next # 节点断开后的下一个子链表
head, tail = self.reverse(head, tail)
# 把子链表重新接回原链表
pre.next = head
tail.next = nex
# 移动 pre 和 head 到下一个位置
pre = tail
head = tail.next
return hair.next- 复杂度分析：
- 时间复杂度：
- 第一轮要合并 n/2 组链表，每一组时间 O(2m)
- 第二轮要合并 n/4 组链表，每一组时间 O(4m)
- 最后一轮要合并 n/n 组链表，每一组时间O(nm)
- 每一轮的时间复杂度为O(nm)，最终时间复杂度为 O(nmlogn)
- 空间复杂度：
- 空间复杂度：O(logn)，递归栈大小，每次都是二分
- 时间复杂度：
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
n = len(lists)
if n == 0: return None # 两种递归终止条件，链表个数为0
if n == 1: return lists[0] # 链表长度为1
mid = n // 2 # 对链表个数一分为二进行合并，递归直到满足终止条件
return self.mergeTwoLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:]))
# 迭代写法
def mergeTwoLists(self, node1, node2):
"""这里其实就是合并两个有序链表"""
dummy = cur = ListNode()
while node1 and node2:
if node1.val <= node2.val:
cur.next = node1
node1 = node1.next
else:
cur.next = node2
node2 = node2.next
cur = cur.next
cur.next = node1 if node1 else node2
return dummy.next核心方法：使用堆，也就是队列优先的方法。一边弹出堆中最小元素，一边利用链表性质，向堆中加入弹出元素的所在链表的下一个节点元素。
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if len(lists)==0: return None
if len(lists)==1: return lists[0]
head=ListNode() # 定义链表的伪头结点
h = head # 定义链表的指针
que = []
# 初始化堆que，完成后堆的所有元素来自lists中每个链表的头结点的值和链表的索引
for i in range(len(lists)):
if lists[i]:
heapq.heappush(que, (lists[i].val,i))
while que :
# 当堆中不为空，逐次弹出最小的元素及其所在链表的索引
# 将最小元素连接在新链表上
val_min, ind_min = heapq.heappop(que)
h.next = ListNode(val_min)
h=h.next
# 被添加元素所在链表后移一个，得到下一个节点
lists[ind_min] = lists[ind_min].next
if lists[ind_min]:
# 如果下一个节点不为空，就将下一个节点值及其链表索引加入堆中，重新排成一个最小堆
heapq.heappush(que, (lists[ind_min].val, ind_min))
return head.next147，对链表进行插入排序，中等
核心方法：插入排序，将节点插入到已经排好序的链表中
-
对于链表，头节点的下一个节点作为当前节点开始进行插入，原来头节点作为已经排好序的节点序列
-
首先判断当前节点是否比节点序列的最后一个节点大，如果是，则直接接在后面（也就是以排好链表的指针向后移一位）
-
如果否，创建新指针，从节点头开始向后移，如果新指针指向的节点比当前节点小，那么指针就向后移；一旦找到一个节点比当前节点大，那么交换这两个指针
-
更新当前节点
时间复杂度：$O(n^2)$
空间复杂度：$O(1)$
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
# 创建哨兵节点，插入head前的节点可以接在dummy后面
dummy = ListNode(0, head)
# 记录已经排好序的链表
done = head
# 当前需要插入的节点
curr = head.next
while curr:
if curr.val >= done.val:
# 如果当前节点本身就是大于前一个节点的，那就直接接在后面
done = done.next
else:
# 从头开始寻找插入位置
prev = dummy
while prev.next.val <= curr.val:
# 只要小于当前节点，指针就往后移一位
prev = prev.next
# 将当前节点进行插入
done.next = curr.next
curr.next = prev.next
prev.next = curr
curr = done.next
return dummy.next160，相交链表，简单
核心方法：哈希表
遍历一个链表A，将其每一个节点都加入哈希集合中；遍历链表B，如果这个遍历到的节点在哈希集合中，那么这个节点就是两个链表的相交节点。
时间复杂度：O(m+n)，m，n为两个链表的长度
空间复杂度：O(m)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
visited = set()
tmp = headA
while tmp:
visited.add(tmp)
tmp = tmp.next
tmp = headB
while tmp:
if tmp in visited:
return tmp
tmp = tmp.next
return None核心方法：双指针
两个链表都不为空时，使用两个指针分别指向两个链头节点。每一向前移动一位，如果指针 pA 为空，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点；当指针 pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者null
时间复杂度：O(m+n)
空间复杂度：O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if not headA or not headB:
return None
pa, pb = headA, headB
while pa != pb:
pa = pa.next if pa else headB
pb = pb.next if pb else headA
return pa138，复制带随机指针的链表，中等
核心方法：哈希表 + DFS
这个题看着有点绕，实际上是一个关于哈希表的题目。链表本身next指针能够保证每个节点都被遍历到，但是random指针做不到这一点；另一当面，random指针能够将next顺序连接的结果变为图，这是next指针做不到的。在遍历复制的过程中，我们需要一个哈希表来存储当前节点是否已经访问过了，访问过就直接返回之前访问的结果，否则random指针会使得DFS产生死循环。
而复制的过程，其实就是获取当前节点的值和其next，random指针指向的对象
时间复杂度：O(n)，n为节点数目
空间复杂度：O(n)，维护回溯的栈，同时记录已经被复制过的节点
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def __init__(self):
self.visited = {} # 创建哈希表，存储访问过的节点
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
# 递归终止条件
return None
if head in self.visited:
# 如果这个节点已经访问过了，那么返回从哈希表中找到的这个节点
return self.visited[head]
# 新建这个节点，首先添加它的值
node = Node(head.val, None, None)
# 在哈希表中进行添加
self.visited[head] = node
# 分别添加next和random指针指向的对象
node.next = self.copyRandomList(head.next)
node.random = self.copyRandomList(head.random)
return node核心方法：迭代
不使用递归的方法，使用迭代，从头遍历链表头节点，新建节点，就当前遍历节点的值赋给新节点，获取当前遍历的next节点和random节点给新建节点（如果新建节点已经在哈希表中，那么直接返回；否则新建一个next节点或random节点，将其赋值给新建节点的next或random）
时间复杂度：O(n)
空间复杂度：O(n)
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def __init__(self):
self.visited = {}
def getClonedNode(self, node):
# 如果新节点的next或random节点不在哈希表中，就新创建一个，然后返回这个节点
if node:
if node not in self.visited:
self.visited[node] = Node(node.val, Node, None)
return self.visited[node]
return None
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return None
old_node = head
new_node = Node(old_node.val, None, None)
self.visited[old_node] = new_node
while old_node != None:
new_node.next = self.getClonedNode(old_node.next)
new_node.random = self.getClonedNode(old_node.random)
# 新节点和后节点向后移动一个
old_node = old_node.next
new_node = new_node.next
return self.visited[head]核心方法：将每个复制的节点都放在原来对应节点的旁边，创造一个就节点和新节点交错的链表；然后迭代这个新旧节点交错的链表，并用旧节点的random指针去更新对应新节点的random指针；同样的方法和目的去更新next节点。
时间复杂度：O(n)
空间复杂度：O(1)
class Solution(object):
def copyRandomList(self, head):
if not head:
return None
# 创建一个新的扭曲链表，同时包含原始节点和复制节点
ptr = head
while ptr:
# 依次复制当前节点，将其添加到原节点的下一个，也就是执行插入操作
new_node = Node(ptr.val, None, None)
new_node.next = ptr.next
ptr.next = new_node
ptr = ptr.next.next
ptr = head
while ptr:
# 更新当前节点的random指针到新建的节点上
ptr.next.random = ptr.random.next if ptr.random else None
ptr = ptr.next.next
ptr_old = head
ptr_new = head.next
head_old = head.next
while ptr_old:
# 修改旧节点的next指针到新节点上，也就是将新链表拆分为新旧两个链表
ptr_old.next = ptr_old.next.next
ptr_new.next = ptr_new.next.next id ptr_new.next else None
ptr_old = ptr_old.next
ptr_new = ptr_new.next
return head_old