在Python中合并两个链表的指定区间

在Python中合并两个链表的指定区间

假设我们有两个长度分别为m和n的链接列表L1和L2,我们还有两个位置a和b。我们必须从L1中从a-th节点到节点b-th节点删除节点,并在其中合并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
  • while temp有下一个节点,do
    • temp := temp的下一个节点
  • tail2 := temp
  • count := 0
  • temp := L1
  • end1 := null,start3 := null
  • while temp不为null,do
    • 如果计数与a-1相同,则
      • end1 := temp
    • 如果计数与b + 1相同,则
      • start3 := temp
      • 退出循环
    • temp := temp的下一个节点
    • 计数 := 计数 + 1
  • next of end1 := head2
  • next of tail2 := start3
  • 返回 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))

输入

[1,5,6,7,1,6,3,9,12], [5,7,1,6], 3, 6

输出

“`python
[1, 5, 6, 5, 7, 1, 6, 9, 12, ]

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程