Description:Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.
Link: https://leetcode.com/problems/merge-two-sorted-lists/
What you need to know: basic functions of linked list, such as insert, delete and add (refer to https://blog.csdn.net/qq_34364995/article/details/80787090).
想法：当我们对链表的操作还不是很熟悉时，不妨先用普通的list来构思解题思路，然后把全部的function换成链表的操作。所以如果是对 two sorted list排序：
l3 = [] while j < len(l2): while i < len(l1) and l1[i] <= l2[j]: l3.append(l1[i]) i += 1 l3.append(l2[j]) j += 1 return l3
全部换成 linked list:
head = ListNode() p = head while l2: while l1 and (l1.val <= l2.val): p.next = l1 p = p.next l1 = l1.next p.next = l2 p = p.next l2 = l2.next return head.next
考虑特殊情况: (1) one of l1 and l2 is None, and (2) l1 = [2], l2 = [1], 需要将剩余的尾部连上去，final version:
# 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, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ head = ListNode() p = head if l1 is None: return l2 if l2 is None: return l1 while l2: while l1 and (l1.val <= l2.val): p.next = l1 p = p.next l1 = l1.next p.next = l2 p = p.next l2 = l2.next if l1: p.next = l1 if l2: p.next = l2 return head.next
日期：2020-11-13 (Time and efforts are always needed. Closer to the deadline.)