对于开发工程师来说,实现两个链表合并为一个有序链表是必须掌握的技能之一。Python语言在链表处理上非常便利,本文将从多个方面详细阐述如何利用Python实现两个链表合并为一个有序链表。
一、链表基础知识
链表是一种常用的数据结构,由一系列节点组成。每个节点由数据和指向下一个节点的指针组成,最后一个节点的指针指向NULL。链表分为单向链表和双向链表。
单向链表的每个节点只有一个指向下一个节点的指针,从头节点往后遍历;而双向链表的每个节点有两个指针,一个指向前一个节点,一个指向后一个节点,可以双向遍历。
二、合并两个链表基本思路
假设有两个单调不降链表,将它们合并为一个单调不降链表。
比较两个链表的头结点,将较小值的结点加入到新链表中,并将该结点从原链表头结点剥离。之后再与另一个链表的头结点进行比较,以此类推,直到其中一个链表为空,则将另一个链表的所有结点直接加入新链表中,最后得到一个有序链表。
三、实现代码
class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: head = ListNode(0) # 定义一个哑节点 pre = head while l1 and l2: if l1.val < l2.val: pre.next = l1 l1 = l1.next else: pre.next = l2 l2 = l2.next pre = pre.next # 保留新链表的尾部 pre.next = l1 if l1 else l2 # 处理剩余节点 return head.next
四、测试样例
对代码进行测试是不可缺少的环节,下面给出两个链表测试样例。
样例1:
l1 = ListNode(1) l1.next = ListNode(2) l1.next.next = ListNode(4) l2 = ListNode(1) l2.next = ListNode(3) l2.next.next = ListNode(4) s = Solution() res = s.mergeTwoLists(l1, l2) while res: print(res.val, end=' ') res = res.next
输出结果为:1 1 2 3 4 4
样例2:
l1 = ListNode(-9) l1.next = ListNode(3) l2 = ListNode(5) l2.next = ListNode(7) s = Solution() res = s.mergeTwoLists(l1, l2) while res: print(res.val, end=' ') res = res.next
输出结果为:-9 3 5 7
五、总结
本文详细介绍了如何利用Python实现两个链表合并为一个有序链表。通过对链表基础知识和合并思路的讲解,读者可以更好地理解代码实现。
值得注意的是,在进行链表操作时,一定要小心指针的使用,防止出现死循环或者空指针异常情况。