iT邦幫忙

0

leetcode with python:21. Merge Two Sorted Lists

題目:

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.

給定兩個排序過的linked list,將兩個整合成一個新的 sorted linked list

整體來說,這題便是linked list操作的練習

# 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:      #一旦其中一個是None,兩者就不用整合了
            return list2
        if not list2:
            return list1
            
        ll=ListNode() #紀錄欲回傳linkedlist的head
        ans=ll
        
        while True:
            if list1.val>=list2.val:
                ll.next=list2
                list2=list2.next
            else:
                ll.next=list1
                list1=list1.next
            ll=ll.next
            
            if list1==None:
                ll.next=list2
                break
            if list2==None:
                ll.next=list1
                break
        return ans.next

將兩linked list的值逐一比較,較小的值填入新的linked list(ll)內,給值的linked list進入下一項
直到其中一個linked list跑完,另外一個還有剩的話就將剩下全部接到ll之後(因為剩下的值都>ll的最後一項)
最終ll便成為新的sorted merged linked list
最後執行時間為34ms(faster than 97.14%)

那我們下題見


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

0
JohnWick
iT邦新手 5 級 ‧ 2022-06-22 15:57:52

十分有幫助,牛逼阿老鐵

我要留言

立即登入留言