python实现合并两个排序的链表

下面是“python实现合并两个排序的链表”的完整攻略：

1. 题目描述

给定两个排好序的链表，将这两个链表合并成一个新的链表并返回。

例如，输入链表1为 1->2->4，链表2为 1->3->4，则合并后的新链表为 1->1->2->3->4->4。

2. 思路

• 定义新链表的头结点；
• 定义一个游标，指向新链表的头结点，同时遍历原有的两个链表；
• 比较原有两个链表的当前结点，将较小值的结点作为新链表的下一个结点，并将游标后移；
• 将较小值的链表也后移一位，重复上述过程直到有一条链表为空，将另一条链表剩余结点直接连接上新链表的尾部；
• 最后返回新链表的首节点。

3. 代码实现

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def mergeTwoLists(self, l1, l2):
        dummy = ListNode(0)    # 定义新链表的头结点
        curr = dummy    # 定义游标，初始指向头结点
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next    # 游标后移
        curr.next = l1 if l1 else l2    # 将剩余链表连接到新链表尾部
        return dummy.next    # 返回新链表的首节点

4. 示例说明

示例一：

链表1：1->2->4

链表2：1->3->4

合并后的新链表：1->1->2->3->4->4

l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(4)

l2 = ListNode(1)
l2.next = ListNode(3)
l2.next.next = ListNode(4)

sol = Solution()
new_list = sol.mergeTwoLists(l1, l2)

while new_list:
    print(new_list.val, end=' ')
    new_list = new_list.next

输出结果为：1 1 2 3 4 4

示例二：

链表1：1->3->4->7

链表2：2->5->6->8

合并后的新链表：1->2->3->4->5->6->7->8

l1 = ListNode(1)
l1.next = ListNode(3)
l1.next.next = ListNode(4)
l1.next.next.next = ListNode(7)

l2 = ListNode(2)
l2.next = ListNode(5)
l2.next.next = ListNode(6)
l2.next.next.next = ListNode(8)

sol = Solution()
new_list = sol.mergeTwoLists(l1, l2)

while new_list:
    print(new_list.val, end=' ')
    new_list = new_list.next

输出结果为：1 2 3 4 5 6 7 8

以上就是“python实现合并两个排序的链表”的完整攻略。