leetcode 1669. Merge In Between Linked Lists(python)

語言: CN / TW / HK

本文已參與「掘力星計劃」,贏取創作大禮包,挑戰創作激勵金。

描述

You are given two linked lists: list1 and list2 of sizes n and m respectively.

Remove list1's nodes from the ath node to the bth node, and put list2 in their place.

The blue edges and nodes in the following figure incidate the result:

Build the result list and return its head.

Example 1:

Input: list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [0,1,2,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.

Example 2:

Input: list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
Output: [0,1,1000000,1000001,1000002,1000003,1000004,6]
Explanation: The blue edges and nodes in the above figure indicate the result.

Note:

3 <= list1.length <= 10^4
1 <= a <= b < list1.length - 1
1 <= list2.length <= 10^4

解析

根據題意,就是給出了兩個長度分別為 n 和 m 的連結串列 list1 和 list2 ,同時又給出了兩個數字 a 和 b ,題目要求我們移除 list1 中從 ath 節點到 bth 節點,並且將 list2 接入到移除的節點的位置。思路比較簡單:

  • 先初始化變數 L1_H 為 list1 表示一會要將 list2 接入 list1 中的頭節點,初始化變數 L1_tail 為 list1 表示在 list2 之後要接上的 list1 的剩餘尾部節點。
  • 使用 while 迴圈不斷往後尋找之後將 list2 接入 list1 的頭節點 L1_H
  • 使用 while 迴圈不斷往後尋找 list1 的尾部剩餘節點 L1_tail
  • 將 list2 接到 L1_H 之後
  • 使用 while 迴圈不斷往後尋找 list2 的尾節點
  • 將 L1_tail 接入到 list2 的尾節點之後
  • 返回 list1 即是最新的拼接好的連結串列

解答

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def mergeInBetween(self, list1, a, b, list2):
        """
        :type list1: ListNode
        :type a: int
        :type b: int
        :type list2: ListNode
        :rtype: ListNode
        """
        L1_H = list1
        L1_tail = list1
        while a-1>0:
            L1_H = L1_H.next
            a -= 1
        while b-1>=0:
            L1_tail = L1_tail.next
            b -= 1
        L1_H.next = list2
        while list2:
            if list2.next:
                list2 = list2.next
            else:
                break
        list2.next = L1_tail.next
        return list1

執行結果

Runtime: 676 ms, faster than 16.10% of Python online submissions for Merge In Between Linked Lists.
Memory Usage: 24.5 MB, less than 61.86% of Python online submissions for Merge In Between Linked Lists.

解析

還可以對上述的過程簡化一下,思路和上面一樣。其實這道題按照正常的邏輯思維把程式碼寫出來就肯定是對的,只不過高手可能對程式碼的組織更加緊湊合理,我有點不自信去論壇看其他大神的解法,發現其實基本上都是大同小異的對兩個連結串列的遍歷和拼接操作。我覺得可能對不起這個 Medium 的難度。

解答

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def mergeInBetween(self, list1, a, b, list2):
        """
        :type list1: ListNode
        :type a: int
        :type b: int
        :type list2: ListNode
        :rtype: ListNode
        """
        head = list1
        for _ in range(a-1):
            head = head.next
        cur = head.next
        for _ in range(b-a):
            cur = cur.next
        head.next = list2
        while head.next:
            head = head.next
        if cur.next:
            head.next = cur.next
        return list1

執行結果

Runtime: 469 ms, faster than 93.22% of Python online submissions for Merge In Between Linked Lists.
Memory Usage: 24.8 MB, less than 11.02% of Python online submissions for Merge In Between Linked Lists.

原題連結:https://leetcode.com/problems/merge-in-between-linked-lists/

您的支援是我最大的動力