- 合并K个升序链表（困难）
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
知识补充：Python heapq模块
heap = [] # 创建了一个空堆 heapq.heappush(heap, item) # 往堆中插入元素 heapq.heappop(heap) # 弹出堆顶元素并返回 heap[0] # 查看堆顶元素 heapq.heapify(x) # 将一个列表转化为堆 heapq.heapreplace(heap, item) # 先弹出后插入，返回值为堆顶元素 heapq.heappushpop(heap, item) # 先插入后弹出，返回值为堆顶元素 heapq.merge(*iterable) # 合并多个堆并返回 heapq.nlargest(n, iterbale, key=None) # 返回堆中最大的n个元素 heapq.nsmallest(n, iterable, key=None) # 返回堆中最小的n个元素
转自：https://blog.csdn.net/minxihou/article/details/51857518
# 方法一：优先队列（堆）
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
import heapq
prevhead = ListNode(-1) # 哨兵结点
prev = prevhead
heap = [] # 定义空堆
# for循环：将所有链表中的所有结点值和链表下标插入堆中（暗含排序操作）
for i in range(len(lists)): # 对于每一个链表
while lists[i]: # 如果当前链表非空
heapq.heappush(heap, (lists[i].val, i)) # 将当前结点值和链表下标插入堆
lists[i] = lists[i].next # 当前链表指针后移
while heap: # 堆非空
val, index = heapq.heappop(heap) # 弹出堆顶元素
prev.next = ListNode(val) # 将prev的next指针指向最小值结点
prev = prev.next # prev指针后移
return prevhead.next # 哨兵结点，好用！
# 方法二：分治法
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if lists is None:
return
return self.merge(lists, 0, len(lists)-1)
def merge(self, lists, left, right):
if left == right: # 递归停止条件：自己与自己合并
return lists[left]
# 分而治之
mid = left + (right - left) // 2
l1 = self.merge(lists, left, mid) # 递归合并左半边链表，结果为一个链表
l2 = self.merge(lists, mid+1, right) # 递归合并右半边链表，结果为一个链表
return self.mergeTwoLists(l1, l2) # 合并两个链表
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
# 任意一个为空，递归结束
if l1 is None:
return l2
elif l2 is None:
return l1
# 将较小结点的next指针指向其余结点的合并结果
elif l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
转自：https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/leetcode-23-he-bing-kge-pai-xu-lian-biao-by-powcai/
- 两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
### 我的解法（自认为做的还行，时间和空间都击败了60+嘻嘻嘻）
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
dummy = ListNode(0)
prev = dummy
if head is None:
return
while True:
if head.next:
prev.next = ListNode(head.next.val)
prev = prev.next
prev.next = ListNode(head.val)
prev = prev.next
else:
prev.next = ListNode(head.val)
break
if head.next.next:
head = head.next.next
else:
break
return dummy.next
### 官方解法
# 方法一：递归
# 时间复杂度：O(n)
# 空间复杂度：O(n)
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
# 递归结束条件：链表没有结点或只有一个结点（无法交换）
if not head or not head.next:
return head
newHead = head.next # 原链表第二个结点作为新链表的头结点
head.next = self.swapPairs(newHead.next) # 将head的next指针指向剩余结点交换的结果
newHead.next = head # 再将新链表头结点的next指针指向head，得到结果
return newHead
# 方法二：迭代
# 每次交换temp结点后面的两个结点，并将temp后移两位
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
dummyHead = ListNode(0)
dummyHead.next = head # dummyHead->head
temp = dummyHead # temp->head
while temp.next and temp.next.next: # temp后两个结点都存在
node1 = temp.next
node2 = temp.next.next
temp.next = node2 # temp->node2
node1.next = node2.next # node1->node2.next
node2.next = node1 # temp->node2->node1->node2.next
temp = node1 # temp指向node1（后移两位）
# 只剩一个结点或无结点时，直接结束循环，即不需要做任何操作
return dummyHead.next
转自：https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/liang-liang-jiao-huan-lian-biao-zhong-de-jie-di-91/
