Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 주어진 두 연결 목록의 합집합을 찾는 프로그램

<시간/>

두 개의 정렬된 연결 목록 L1과 L2가 있다고 가정하면 주어진 두 목록의 합집합인 정렬된 새 연결 목록을 반환해야 합니다.

따라서 입력이 L1 =[10,20,30,40,50,60,70] L2 =[10,30,50,80,90]인 경우 출력은 [10, 20, 30, 40, 50, 60, 70, 80, 90, ]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • solve() 함수를 정의합니다. L1, L2가 걸립니다.
  • L1이 비어 있으면
    • 반환 L2
  • L2가 비어 있으면
    • 반환 L1
  • L1의 값
  • res :=L1
  • res의 다음:=solve(L1, L2의 다음)
  • 그렇지 않으면 L2의 값
  • res :=L2
  • res의 다음 :=solve(L2, L1의 다음)
  • 그렇지 않으면
    • res :=L1
    • res의 다음 :=solve(L1의 다음, L2의 다음)
  • 반환 결과
  • 이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

    예시

    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(']')
    class Solution:
       def solve(self, L1, L2):
          if not L1:
             return L2
          if not L2:
             return L1
          if L1.val < L2.val:
             res = L1
             res.next = self.solve(L1.next, L2)
          elif L2.val < L1.val:
             res = L2
             res.next = self.solve(L2.next, L1)
          else:
             res = L1
             res.next = self.solve(L1.next, L2.next)
       return res
    ob = Solution()
    L1 = make_list([10,20,30,40,50,60,70])
    L2 = make_list([10,30,50,80,90])
    print_list(ob.solve(L1, L2))

    입력

    [10,20,30,40,50,60,70], [10,30,50,80,90]

    출력

    [10, 20, 30, 40, 50, 60, 70, 80, 90, ]