두 개의 정렬된 연결 목록 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의 다음)
- 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, ]