T21 合并两个有序链表

题目描述如下：

解题思路：

先不看那两个链表，首先搞个head，pcur，我们只关注pcur应该接哪个节点，接下来就只要比较两个链表当前的值了，用两个指针p1，p2指向两个链表l1，l2. 对于不同的情况进行操作（主要指其中一个为空和两个都不为空的情况，如果两个都为空就结束了）

两个都不为空，将p1, p2中比较小的连上

有一个为空，把剩下的连上并结束

# 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]:
       p1 = list1
       p2 = list2
       pcur = None
       phead = None
       while p1 is not None or p2 is not None:
           # 初始化head
           if pcur is None:
               if p1 is None and p2 is None:
                   break
               elif p1 is None and p2 is not None:
                   pcur = p2
                   phead = pcur
                   p2 = p2.next
                   break
               elif p1 is not None and p2 is None:
                   pcur = p1
                   phead = pcur
                   p1 = p1.next
                   break
               else:
                   if p1.val <= p2.val:
                       pcur = p1
                       phead = pcur
                       p1 = p1.next
                   else:
                       pcur = p2
                       phead = pcur
                       p2 = p2.next
​
           # 开始链接到head链表中
           if p1 is not None and p2 is not None:
               if p1.val <= p2.val:
                   pcur.next = p1
                   pcur = pcur.next
                   p1 = p1.next
               else:
                   pcur.next = p2
                   pcur = pcur.next
                   p2 = p2.next
​
           if p1 is not None and p2 is None:
               pcur.next = p1
               p1 = None
           if p1 is None and p2 is not None:
               pcur.next = p2
               p2 = None
           print(p1, p2)
​
       return phead

结果如下：

优化：

判断放在了循环里面，导致每次都需要判断一次，包括head为空的判断和是否其中有一个链表为空的判断。

把这几个过程分开，head为空的放到外面，有一个链表为空的也放出来

优化后代码：

# 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]:
       if not list1 and not list2:
           return None
       if list1 and not list2:
           return list1
       if list2 and not list1:
           return list2
       p1 = list1
       p2 = list2
       pcur = None
       phead = None
       # 初始化pcur
       if list1.val < list2.val:
           pcur = list1
           list1 = list1.next
       else:
           pcur = list2
           list2 = list2.next
       phead = pcur
# 两个链表都不为空的情况
       while list1 and list2:
           if list1.val < list2.val:
               pcur.next = list1
               list1 = list1.next
               pcur = pcur.next
           else:
               pcur.next = list2
               list2 = list2.next
               pcur = pcur.next
# 其中一个链表为空的情况
       if list1 and not list2:
           pcur.next = list1
       else:
           pcur.next = list2
​
       return phead

结果如下：

芜湖舒服了！