LeetCode 21. 合并两个有序链表

题目

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

例：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

方法

• result 和 curr 分别指向链表的头节点，curr 指向当前节点
• 循环直至两个链表 list1 和 list2 均为空
  • 若两个链表均不为空，判断指针指向的节点值
    • 若 list1 指向的节点值小于等于 list2 指向的节点值，将 list1 指向的节点值放入链表，并更新 list1 指向的节点
    • 若 list1 指向的节点值大于 list2 指向的节点值，将 list2 指向的节点值放入链表，并更新 list2 指向的节点
  • 若链表 list1 非空链表 list2 为空，那么将 list1 指向的节点值放入链表，并更新 list1 指向的节点
  • 若链表 list1 为空链表 list2 非空，那么将 list2 指向的节点值放入链表，并更新 list2 指向的节点
• 将当前指向新链表的指针 curr 指向下一个节点
• 返回新链表

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        result = curr = ListNode()
        while list1 or list2:
            if list1 and list2:
                if list1.val <= list2.val:
                    curr.next = ListNode(list1.val)
                    list1 = list1.next
                else:
                    curr.next = ListNode(list2.val)
                    list2 = list2.next
            elif list1:
                curr.next = ListNode(list1.val)
                list1 = list1.next
            else:
                curr.next = ListNode(list2.val)
                list2 = list2.next
            curr = curr.next
        return result.next