小黑星巴克冰镇浓缩leetcode之旅:21. 合并两个有序链表

小黑的答案

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        a_link = list1
        b_link = list2
        head = ListNode()
        link = head
        # 直到一个链表打印完毕
        while a_link and b_link:
            if a_link.val > b_link.val:
                link.next = b_link
                link = b_link
                b_link = b_link.next
            else:
                link.next = a_link
                link = a_link
                a_link = a_link.next
        # 有一个链表遍历完毕
        if a_link:
            link.next = a_link
        else:
            link.next = b_link
        return head.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

递归法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 表1遍历完毕
        if not list1:
            return list2
        # 表2遍历完毕
        elif not list2:
            return list1
        # 判断两个头结点谁小，小的则拎出来
        elif list1.val > list2.val:
            list2.next = self.mergeTwoLists(list1,list2.next)
            return list2
        else:
            list1.next = self.mergeTwoLists(list1.next,list2)
            return list1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

迭代法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 辅助头结点
        head = ListNode(-1)
        prev = head
        # 遍历两个表，直到一个为空
        while list1 and list2:
            if list1.val > list2.val:
                prev.next = list2
                list2 = list2.next
            else:
                prev.next = list1
                list1 = list1.next
            prev = prev.next
        # 将prev链接到非空的链表中
        prev.next = list1 if list1 else list2
        return head.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

小黑生活现状