python-3.x 第1669条在链接列表之间合并- Leetcode -测试失败

y53ybaqx  于 2022-12-05  发布在  Python
关注(0)|答案(1)|浏览(117)

我正在处理LeetCode问题1669. Merge In Between Linked Lists
您将获得两个链接列表:分别为nmlist1list2
删除list1的节点,从第a个节点到第b个节点,并将list2放在它们的位置。
下图中的蓝色边和节点表示结果:

  • 生成结果列表并返回其头部。*

约束条件:

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

下面是我的代码:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        
        slow = fast = list1
        temp1 = temp2 = list2

        slowslow = fastfast = list1

        if slow != a:
            slow = slow.next

        if slowslow.val != a-1:
            slowslow = slowslow.next

        if fast != b:
            fast = fast.next
            fastfast = fast.next

        while temp2.next:
            temp2 = temp2.next

        slowslow.next = temp1
        temp2.next = fastfast

        return list1

第一个测试用例失败:
输入:

[0,1,2,3,4,5]
3
4
[1000000,1000001,1000002]

我的输出:

[0,1000000,1000001,1000002,2,3,4,5]

预期输出:

[0,1,2,1000000,1000001,1000002,5]

我尝试将slowslow指针放在a之前,将fastfast指针放在b之后,然后将slowslow连接到temp1,将temp2连接到fastfast
但不知何故,这是行不通的。我的尝试有什么问题吗?
我是链表的新手,希望能有一个简单的改变,甚至更简单的替代方法。

ac1kyiln

ac1kyiln1#

一些问题:

  • slow != a是始终为False的条件,因为slowListNode对象,而aintfast != b也会出现同样的问题。
  • slowslow.val != a-1是错误的,因为问题中没有任何内容需要查看列表中的 valuesaindex,而不是 value
  • 您的代码会将slow设置为第一个列表的第一个节点或第二个节点。没有循环可以保证slow会引用索引a之前的节点。fast也存在同样的问题。

以下是工作代码:

class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        # Find node that precedes index a in first list
        left = list1
        for i in range(a - 1):
            left = left.next
        # Find node that follows index b in first list
        right = left
        for i in range(b - a + 2):
            right = right.next
        # Find tail node of second list            
        tail = list2
        while tail.next:
            tail = tail.next
        # Make the connections
        left.next = list2
        tail.next = right
        return list1

相关问题