Python 中用于在链表之间进行合并的程序

pythonserver side programmingprogramming更新于 2025/11/30 7:08:17

假设我们有两个链表 L1 和 L2，长度分别为 m 和 n，我们还有两个位置 a 和 b。我们必须从 L1 中删除从第 a 个节点到第 b 个节点的节点，并在其间合并 L2。

因此，如果输入为 L1 = [1,5,6,7,1,6,3,9,12] L2 = [5,7,1,6] a = 3 b = 6，则输出为 [1, 5, 6, 5, 7, 1, 6, 9, 12]

为了解决这个问题，我们将遵循以下步骤 −

head2 := L2, temp := L2
当 temp 有下一个节点时，执行
- temp := next of temp
tail2 := temp
count := 0
temp := L1
end1 := null, start3 := null
当 temp 不为 null 时，执行
- 如果 count 与 a-1 相同，则
  - end1 := temp
- 如果 count 与 b+1 相同，则
  - start3 := temp
  - 退出循环
- temp := next of temp
- count := count + 1
next of end1 := head2
next of tail2 := start3
return L1

示例

让我们看看下面的实现以便更好地理解 −

class ListNode:
   def __init__(self, data, next = None):
      self.val = data
      self.next = next

def make_list(elements):
   head = ListNode(elements[0])
   for element in elements[1:]:
      ptr = head
      while ptr.next:
         ptr = ptr.next
      ptr.next = ListNode(element)
   return head

def print_list(head):
   ptr = head
   print('[', end = "")
   while ptr:
      print(ptr.val, end = ", ")
      ptr = ptr.next
   print(']')

def solve(L1, L2, a, b):
   head2 = temp = L2
   while temp.next:
      temp = temp.next
   tail2 = temp

   count = 0
   temp = L1
   end1, start3 = None, None
   while temp:
      if count == a-1:
         end1 = temp
      if count == b+1:
         start3 = temp
         break
      temp = temp.next
      count += 1

   end1.next = head2
   tail2.next = start3
   return L1

L1 = [1,5,6,7,1,6,3,9,12]
L2 = [5,7,1,6]
a = 3
b = 6
print_list(solve(make_list(L1), make_list(L2), a, b))