파이썬에서 연결 리스트를 병합하는 프로그램

각각 길이가 m과 n인 두 개의 연결 리스트 L1과 L2가 있다고 가정하고 두 위치 a와 b도 있습니다. L1에서 노드 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, 온도 :=L2
• temp에 다음 노드가 있는 동안 do
  • temp :=다음 temp
• tail2 :=온도
• 카운트:=0
• 온도 :=L1
• end1 :=null, start3 :=null
• temp가 null이 아닌 동안 do
  • count가 -1과 같으면
    • end1 :=임시
  • 카운트가 b+1과 같으면
    • start3 :=임시
    • 루프에서 나오다
  • temp :=다음 temp
  • 카운트 :=카운트 + 1
• end1 다음:=head2
• 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

출력

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