21. Merge Two Sorted Lists

题目描述

---

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

示例：

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

我的解法——扫描+比较大小（AC）

• 链表有序合并也是数据结构里边的经典题目了。大体思路就是分别扫描两个链表，比较两个节点的大小值，把较小的节点值尾插到结果链表屁股后边，然后再次扫描两个链表，直到其中某一个链表或者两条链表同时结束。如果是某条链表提前结束则应将另一条链表的其余节点都接到结果链表上。
• 注意点：
  • 若其中一个链表为空，则直接返回另一个。
  • 优先考虑指针为空的情况避免访问出错
• 时间空间复杂度均为O(n)。
• Beat64%

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

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        
        now = ListNode(0)
        now.next = None
        head = now
        
        while(l1 != None and l2 != None):
            if(l1.val < l2.val):
                now.next = l1
                l1 = l1.next
            else:
                now.next = l2
                l2 = l2.next
            now = now.next
        
        while(l1 != None):
            now.next = l1
            l1 = l1.next
            now = now.next
        while(l2 != None):
            now.next = l2
            l2 = l2.next
            now = now.next
            
        return head.next