剑指offer第二版（Python3）面试题25：合并两个排序的链表，合并K个排序链表

  面试题22&＃xff1a;链表中倒数第k个结点

  面试题24 &＃xff1a;翻转链表

  面试题25 &＃xff1a;合并两个排序的链表&＃xff0c;合并K个排序链表

第4章 解决面试题的思路

第5章 优化时间和空间效率

第6章 面试中的各项能力

第7章 两个面试案例

题目描述
  输入两个单调递增的链表&＃xff0c;输出两个链表合成后的链表&＃xff0c;当然我们需要合成后的链表满足单调不减规则。

  这是一道经常被各公司采用的面试题----《剑指offer》
解题思路
  要求O(1)空间复杂度

解法一&＃xff1a;
  用两个指针p1和p2分别指向两个链表头节点。

1. 比较p1和p2节点值。若p1.val<&＃61;p2.val&＃xff0c;用pre_p1保留p1位置&＃xff0c;然后p1右移一位&＃xff0c;重复步骤1&＃xff1b;若p1.val>p2.val&＃xff0c;则pre_p1.next&＃61;p2&＃xff0c;转入步骤2&＃xff1b;
2. 比较p1和p2节点值。若p2.valp1.val&＃xff0c;则pre_p2.next&＃61;p1&＃xff0c;转入步骤1&＃xff1b;
3. 直到p1或者p2为空。

实战

def Merge(pHead1, pHead2):# write code hereif not pHead1:return pHead2if not pHead2:return pHead1if pHead1.val <&＃61; pHead2.val:new_head &＃61; pHead1else:new_head &＃61; pHead2pre_pHead1, pre_pHead2 &＃61; None, Nonewhile pHead1 and pHead2:while pHead1 and pHead2 and pHead1.val <&＃61; pHead2.val:pre_pHead1 &＃61; pHead1pHead1 &＃61; pHead1.nextif pre_pHead1:pre_pHead1.next &＃61; pHead2pre_pHead1 &＃61; Nonewhile pHead1 and pHead2 and pHead2.val < pHead1.val:pre_pHead2 &＃61; pHead2pHead2 &＃61; pHead2.nextif pre_pHead2:pre_pHead2.next &＃61; pHead1pre_pHead2 &＃61; Nonereturn new_head


上述解法稍显复杂&＃xff0c;代码容易出错。

解法二&＃xff1a;
  示例&＃xff1a;
    链表1&＃xff1a;[1&＃xff0c; 3&＃xff0c; 5&＃xff0c; 7]
    链表2&＃xff1a;[2&＃xff0c;4&＃xff0c; 6&＃xff0c; 8]

  首先分析合并两个链表的过程。从头结点开始&＃xff0c;链表1的头结点值小于链表2的值&＃xff0c;因此链表1的头结点是合并后链表的头结点。我们拿出链表1的头结点&＃xff0c;剩下情况如下&＃xff1a;
    已确定节点&＃xff1a;1
    链表1&＃xff1a;[3&＃xff0c; 5&＃xff0c; 7]
    链表2&＃xff1a;[2&＃xff0c;4&＃xff0c; 6&＃xff0c; 8]
  重复上述过程&＃xff0c;从头结点开始&＃xff0c;链表1的头结点值大于链表2的值&＃xff0c;因此链表2的头结点是合并后链表的头结点。我们拿出链表2的头结点&＃xff0c;剩下情况如下&＃xff1a;
    已确定节点&＃xff1a;1&＃xff0c; 2
    链表1&＃xff1a;[3&＃xff0c; 5&＃xff0c; 7]
    链表2&＃xff1a;[4&＃xff0c; 6&＃xff0c; 8]
  一直重复上述过程&＃xff0c;直到链表1或者链表2为空。这种解法是每次从两个链表的头结点中选出一个来&＃xff0c;这样选出的节点可以确保是非递减的。
实战
循环解法

class Solution:# 返回合并后列表def Merge(self, pHead1, pHead2):# write code herehead &＃61; node &＃61; ListNode(0)while pHead1 and pHead2:if pHead1.val <&＃61; pHead2.val:node.next &＃61; pHead1pHead1 &＃61; pHead1.nextelse:node.next &＃61; pHead2pHead2 &＃61; pHead2.nextnode &＃61; node.nextif pHead1:node.next &＃61; pHead1if pHead2:node.next &＃61; pHead2return head.next


题目描述&＃xff1a;
  合并 k 个排序链表&＃xff0c;返回合并后的排序链表。请分析和描述算法的复杂度。
leetcode

解题思路&＃xff1a;
leetcode

因此&＃xff0c;我们在每一次配对合并的过程中都会遍历几乎全部 N个节点&＃xff0c;并重复这一过程 次。

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val &＃61; x
# self.next &＃61; Noneclass Solution:def mergeKLists(self, lists: List[ListNode]) -> ListNode:amount &＃61; len(lists)interval &＃61; 1while interval < amount:for i in range(0, amount - interval, interval * 2):lists[i] &＃61; self.merge2Lists(lists[i], lists[i &＃43; interval])interval *&＃61; 2return lists[0] if amount > 0 else Nonedef merge2Lists(self, l1, l2):head &＃61; point &＃61; ListNode(0)while l1 and l2:if l1.val <&＃61; l2.val:point.next &＃61; l1l1 &＃61; l1.nextelse:point.next &＃61; l2l2 &＃61; l2.nextpoint &＃61; point.nextif not l1:point.next&＃61;l2else:point.next&＃61;l1return head.next