【朱迪的LeetCode刷题笔记】】21. Merge Two Sorted Lists #Easy #Python

Judie

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:
Input: list1 = [], list2 = []
Output: []

Example 3:
Input: list1 = [], list2 = [0]
Output: [0]


Constraints:
The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.

1. # Definition for singly-linked list.
   
2. # class ListNode(object):
   
3. #     def __init__(self, val=0, next=None):
   
4. #         self.val = val
   
5. #         self.next = next
   
6. class Solution(object):
   
7.     def mergeTwoLists(self, list1, list2):
   
8.         """
   
9.         :type list1: Optional[ListNode]
   
10.         :type list2: Optional[ListNode]
    
11.         :rtype: Optional[ListNode]
    
12.         """
    
13.    

复制代码

https://leetcode.com/problems/me ... on-dummy-explained/

Solution 1
by using variables dummy and temp
dummy is pointing to the start i.e. dummy makes sure we don;t loose the head of the thread (result list)
temp makes the linkes from node to node i.e we are traversing using temp

1. class Solution:
   
2.     def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:   
   
3.         dummy = temp = ListNode(0)
   
4.         while l1 != None and l2 != None: #1
   
5. 
   
6.             if l1.val < l2.val: #2
   
7.                 temp.next = l1 #3
   
8.                 l1 = l1.next #4
   
9.             else:
   
10.                 temp.next = l2
    
11.                 l2 = l2.next
    
12.             temp = temp.next
    
13.         temp.next = l1 or l2  #5
    
14.         return dummy.next #6

复制代码

Solution 2
by doing recursion

1. class Solution:
   
2.     def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:   
   
3.         if not l1 or not l2:
   
4.             return l1 or l2
   
5.         
   
6.         if l1.val <= l2.val: #1
   
7.             l1.next = self.mergeTwoLists(l1.next, l2)
   
8.             return l1
   
9.         else: #2
   
10.             l2.next = self.mergeTwoLists(l1, l2.next)
    
11.             return l2

复制代码

Judy

yinda_peng

yinda_peng

我觉得我也得慢慢习惯看英文，有时候中文的机翻有点看不懂什么意思

Judie

yinda_peng 发表于 2023-5-27 00:33
我觉得我也得慢慢习惯看英文，有时候中文的机翻有点看不懂什么意思

嗯嗯！你生活在哪啊 我是生活在北美

Judie

yinda_peng 发表于 2023-5-27 00:33

别说了别说了 这题我没写出来 看的别人的solution

更离谱的是 我翻我记录 这题我一两年前拿c写出来过

yinda_peng

Judie 发表于 2023-5-27 22:46
嗯嗯！你生活在哪啊 我是生活在北美

在湖南呐，小城市出来的，衡阳人

Judie

yinda_peng 发表于 2023-5-28 00:09
在湖南呐，小城市出来的，衡阳人

那你英文真不错！