简说Python，号主老表，Python终身学习者，数据分析爱好者，从18年开始分享Python知识，原创文章227篇，写过Python、SQL、Excel入门文章，也写过Web开发、数据分析文章，老表还总结整理了一份2022Python学习资料和电子书资源，关注后私信回复：2022 即可领取。
今天给大家分享的书籍《Python程序员面试算法宝典》第一章第九小节：合并两个有序链表。
如果你是第一次看，也许，你可以看看本系列下面的文章：
Smaller And Smarter Python数据结构：链表逆转
Smaller And Smarter Python数据结构：删除无序链表重复结点
Smaller And Smarter Python数据结构：链表相加
Smaller And Smarter Python数据结构：链表进行重新排序
Smaller And Smarter Python数据结构：链表倒数第K个元素+检测单链表环
Smaller And Smarter Python数据结构：翻转链表相邻结点
Smaller And Smarter Python数据结构：翻转链表k个相邻结点
今日问题 ：翻转链表k个相邻结点
""" 目标：写一段程序，合并两个有序链表 例如： 输入-> 1->2->3 输入-> 2->5->6->8 输出-> 1->2->2->3->5->6->8 Goal: write a program to merge two ordered lists For example: Input - > 1 - > 2 - > 3 Input - > 2 - > 5 - > 6 - > 8 Output - > 1 - > 2 - > 2 - > 3 - > 5 - > 6 - > 8 """
解题准备
首先我们写好链表的基本操作，在a_0_base.py文件中，目前包含对链表的定义类，初始化函数，遍历函数。（带头结点）
# -*- coding: utf-8 -*- """ @author = 老表 @date = 2019-10-19 @个人微信公众号 : 简说Python """ # 链表数据结构定义 class ListNode: def __init__(self, x): self.data = x self.next = None class ListOperation: a = 1 # 根据链表数据初始化链表 @staticmethod def init_list(n_list): # 初始化一个头指针 head = ListNode("head") cur = head for i in n_list: node = ListNode(i) cur.next = node cur = node # 相当于 cur = cur.next，后移 return head # 根据链表数据初始化一个有环的链表 @staticmethod def init_ring_list(n_list): # 初始化一个头指针 head = ListNode("head") cur = head for i in n_list: node = ListNode(i) cur.next = node cur = node # 相当于 cur = cur.next，后移 cur.next = head.next.next.next.next # 随意的，让最后一个结点指向第四个结点 return head # 遍历链表 @staticmethod def ergodic_list(head): # print(head.data) cur = head.next while cur: print(cur.data) cur = cur.next # 获取链表长度 @staticmethod def get_len_list(head): cur = head.next len_list = 0 while cur: len_list = len_list + 1 cur = cur.next return len_list
解题
开始程序前需提前导入前面写好的链表基本操作包和结点数据结构，在Linked_list的a_0_base.py中。
from Linked_list.a_0_base import ListOperation
解题思路
""" Method One : 遍历插入法 核心思想：先确定合并后链表的头结点（表头小的）， 然后将两个链表一起遍历，将表头数值大的链表结点 插入链表表头结点数值小的链表。 时间复杂度：O(N) 空间复杂度：O(1) """
功能代码
def merge_two_ordered_list_one(head1, head2): if not head1.next: # 空链表 return head2 # 返回头结点 if not head2.next: # 空链表 return head1 # 返回头结点 # 合并第一步：判断谁的开始结点小，确定返回链表 cur_node1 = head1.next # 记录链表一当前结点 cur_node2 = head2.next # 记录链表二当前结点 if cur_node1.data < cur_node2.data: # 判断表头数值大小 # 链表1的表头小，则将链表2结点插入链表1 head = head1 # 记录合并后链表头结点 cur_node = cur_node1 # 记录合并后链表当前结点 cur_node1 = cur_node1.next # 链表1当前结点后移，遍历 else: # 链表2的表头小，则将链表1结点插入链表2 head = head2 # 记录合并后链表头结点 cur_node = cur_node2 # 记录合并后链表当前结点 cur_node2 = cur_node2.next # 链表2当前结点后移，遍历 # 合并第二步：遍历比较结点大小，依次插入小的结点 while cur_node1 and cur_node2: # 开始遍历插入 if cur_node1.data < cur_node2.data: # 链表1的结点小 cur_node.next = cur_node1 # 将链表1该结点插入合并后的链表（准确来说只是追加） cur_node = cur_node1 # 记录合并后的链表的当前结点 cur_node1 = cur_node1.next # 链表1当前结点后移，继续遍历 else: # 链表2的结点小 cur_node.next = cur_node2 # 将链表2该结点插入合并后的链表（准确来说只是追加） cur_node = cur_node2 # 记录合并后的链表的当前结点 cur_node2 = cur_node2.next # 链表2当前结点后移，继续遍历 # 遍历结束，将未遍历完的链表剩余结点加入到合并后的链表结尾 if cur_node1: # 链表1还未遍历完 cur_node.next = cur_node1 if cur_node2: # 链表2还未遍历完 cur_node.next = cur_node2 return head # 返回头结点
测试代码
# 当然，也许还有别的方法，比如建一个辅助的链表 # 欢迎你说出你的想法 # 程序入口，测试函数功能 if __name__ == "__main__": list_data1 = [1, 2, 3] # 链表1初始化数据 list_data2 = [2, 4, 5, 6] # 链表2初始化数据 head1 = ListOperation.init_list(list_data1) # 初始化链表1，带头结点 head2 = ListOperation.init_list(list_data2) # 初始化链表2，带头结点 ListOperation.ergodic_list(head1) # 未操作前，遍历打印链表1 print("___________________________") ListOperation.ergodic_list(head2) # 未操作前，遍历打印链表2 head = merge_two_ordered_list_one(head1, head2) # 测试方法一 print("---------------------") ListOperation.ergodic_list(head) # 操作后，遍历打印链表
本文代码思路部分来自书籍《Python程序员面试宝典》，书中部分代码有问题或未提供代码，文中已经修改过了，并添加上了丰厚的注释，方便大家学习，后面我会把所有内容开源放到Github上，包括代码，思路，算法图解（手绘或者电脑画），时间充裕的话，会录制视频。
希望大家多多支持。
大家好，我是老表
觉得本文不错的话，转发、留言、点赞，是对我最大的支持。
欢迎关注微信公众号：简说Python
关注后回复：1024，可以领取精选编程学习电子书籍。
如果你觉得文章还不错，请大家点赞分享下。你的肯定是我最大的鼓励和支持。
