在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
- 如果计数与a-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, ]