JZ25 合并两个排序的链表

题意

JZ25 合并两个排序的链表

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

思路

归并排序：每次比较两个头部，从中取出最小的元素，然后依次往后。两个头部即为两个指针，同方向访问，取出元素的指针向后移动。

代码

class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        head = ListNode(None)
        p = head
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                p.next=pHead1
                pHead1=pHead1.next
            else:
                p.next=pHead2
                pHead2=pHead2.next
            p=p.next
        p.next=pHead2 if not pHead1 else pHead1
        return head.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

优化：

class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        head = p = ListNode(None)
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                p.next=pHead1
                pHead1=pHead1.next
            else:
                p.next=pHead2
                pHead2=pHead2.next
            p=p.next
        p.next=pHead1 or pHead2
        return head.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14

or 运算符在这里被用作一种短路逻辑运算符。如果第一个操作数评估为True，则返回第一个操作数，如果第一个操作数评估为False，则返回第二个操作数。在Python中，or 运算符返回第一个真值操作数，如果两个都是假值，则返回最后一个操作数。