LeetCode-21 合并两个有序列表

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

题目：合并两个有序列表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

1
2
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

思路

上次的链表题可参考: LeetCode-2 两数相加

首先需要理解ListNode这个class。

1
2
3
4
5
# Definition for singly-linked list.
class ListNode:
	def __init__(self, x):
         self.val = x
         self.next = None

每个ListNode()都有两个属性，一个是本身的值(val)，另一个则是指向另一个ListNode()对象。比如示例中的输出：7 -> 0 -> 8。其实是三个ListNode()对象，产生的过程如下：

1
2
3
4
5
6
7
8
tmp = ListNode(0)
res = tmp
tmp = ListNode(7)
tmp = tmp.next
tmp.next = ListNode(0)
tmp = tmp.next
tmp.next = ListNode(8)
return res.next

对ListNode这样的链表有了理解之后，本题就相对简单了：

  • 初始化一个outNode=ListNode(None)，用于最终输出，再初始化一个curNode=outNode用于记录当前ListNode。
  • 当l1和l2均非空时:
    • 若l1的值比l2的值大，则curNode.next指向l1，l1向后推移一位：l1=l1.next
    • 若l2的值比l1的值大，则curNode.next指向l2，l2向后推移一位：l2=l2.next
    • 当前节点向后推移一位：curNode = curNode.next
  • 将当前节点指向剩余非空节点
  • 返回结果

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        outNode = ListNode(None)
        curNode = outNode
        while l1 and l2:
            if l1.val < l2.val:
                curNode.next = l1;
                l1 = l1.next
            else:
                curNode.next = l2;
                l2 = l2.next
            curNode = curNode.next
        if l1:
            curNode.next = l1;
        else:
            curNode.next = l2
        return outNode.next

如果大家有更好的方法，欢迎一起探讨。