LeetCode 1669：合并链表代码出错，求排查及优化方案

问题说明 #

给定两个链表list1和list2，长度分别为n和m，需要移除list1中第a个到第b个节点（节点位置从0开始计数），将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

问题排查 #

你的核心思路是对的：找到list1中a节点的前驱、b节点的后继，再把list2接进去，但代码里的节点定位逻辑完全错误：

1. 节点与整数直接比较：比如if slow != a，slow是链表节点对象，a是整数，两者永远不可能相等，这个判断毫无意义，只会让slow移动一次。
2. 用节点值判断位置：if slowslow.val != a-1，链表节点的值和它的位置没有必然联系，比如测试用例里a=3，a-1=2，但如果list1里有重复值或者值不是连续的，这个判断就会失效，而且你只做了一次判断，不会循环移动到目标位置。
3. 后继节点定位错误：fast的移动逻辑同样错误，只移动一次就取next，根本到不了b节点的下一个位置。

修正后的代码 #

# 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:
        # 找到a节点的前驱（第a-1个节点）
        pre_a = list1
        for _ in range(a - 1):
            pre_a = pre_a.next
        
        # 找到b节点的后继（第b+1个节点）
        post_b = list1
        for _ in range(b + 1):
            post_b = post_b.next
        
        # 找到list2的尾节点
        list2_tail = list2
        while list2_tail.next:
            list2_tail = list2_tail.next
        
        # 连接节点
        pre_a.next = list2
        list2_tail.next = post_b
        
        return list1

替代思路（更高效的节点定位） #

上面的代码需要两次遍历list1找pre_a和post_b，其实可以在一次遍历中完成：

class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        current = list1
        # 先走到pre_a的位置
        for _ in range(a - 1):
            current = current.next
        
        # 保存pre_a，然后走到post_b的位置
        pre_a = current
        for _ in range(b - a + 2):
            current = current.next
        
        post_b = current
        
        # 找list2尾节点
        list2_tail = list2
        while list2_tail.next:
            list2_tail = list2_tail.next
        
        pre_a.next = list2
        list2_tail.next = post_b
        
        return list1

这样只需要一次遍历list1的目标区间，减少一次遍历操作。

内容的提问来源于stack exchange，提问作者Prayag Padwal