두 개의 정렬된 연결 목록이 있다고 가정하면 시작 노드에서 끝 노드까지의 최대 합 경로로 구성된 연결 목록을 만들어야 합니다. 최종 목록은 두 입력 목록의 노드로 구성될 수 있습니다.
결과 목록을 생성할 때 교차점(목록에서 동일한 값을 갖는 두 노드)에 대해서만 다른 입력 목록으로 전환할 수 있습니다. 일정한 양의 추가 공간을 사용하여 해결해야 합니다.
따라서 입력이 [6,8,35,95,115,125], [5,8,17,37,95,105,125,135]와 같으면 출력은 [6,8,17,37,95,115,125,135]
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
결과 :=없음
-
이전1 :=a, 현재1 :=a
-
이전2 :=b, 현재2 :=b
-
current1이 None과 같지 않거나 current2가 None과 같지 않은 동안 do
-
res1 :=0, res2 :=0
-
current1 및 current2가 null이 아니고 current1의 데이터가 current2의 데이터와 같지 않은 동안 do
-
현재1의 데이터 <현재2의 데이터인 경우
-
res1 :=res1 + current1 데이터
-
current1 :=current1의 다음
-
-
그렇지 않으면
-
res2 :=res2 + current2 데이터
-
current2 :=current2의 다음
-
-
-
current1이 null이면
-
current2가 null이 아닌 동안 수행
-
res2 :=res2 + current2 데이터
-
current2 :=current2의 다음
-
-
-
current2가 null이면
-
current1이 null이 아닌 동안 수행
-
res1 :=res1 + current1 데이터
-
current1 :=current1의 다음
-
-
-
이전1이 b와 같고 이전2가 b와 같으면
-
결과 :=이전1 일 때 (res1> res2) 그렇지 않으면 이전2
-
-
그렇지 않으면
-
res1> res2인 경우
-
이전2의 다음 :=이전1의 다음
-
-
그렇지 않으면
-
이전1의 다음 :=이전2의 다음
-
-
-
이전1 :=현재1
-
이전2 :=현재2
-
current1이 null이 아니면
-
current1 :=current1의 다음
-
-
current2가 null이 아니면
-
current2 :=current2의 다음
-
-
-
결과의 내용을 표시합니다.
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
class LinkedList(object): def __init__(self, data_set = []): self.head = None if len(data_set) > 0: for item in data_set: self.insert_node(item) class ListNode(object): def __init__(self, d): self.data = d self.next = None def insert_node(self, new_data): new_node = self.ListNode(new_data) new_node.next = self.head self.head = new_node def find_max_sum_list(self, a, b): result = None previous1 = a current1 = a previous2 = b current2 = b while current1 != None or current2 != None: res1 = 0 res2 = 0 while current1 != None and current2 != None and current1.data != current2.data: if current1.data < current2.data: res1 += current1.data current1 = current1.next else: res2 += current2.data current2 = current2.next if current1 == None: while current2 != None: res2 += current2.data current2 = current2.next if current2 == None: while current1 != None: res1 += current1.data current1 = current1.next if previous1 == a and previous2 == b: result = previous1 if (res1 > res2) else previous2 else: if res1 > res2: previous2.next = previous1.next else: previous1.next = previous2.next previous1 = current1 previous2 = current2 if current1 != None: current1 = current1.next if current2 != None: current2 = current2.next while result != None: print(result.data, end = ' ') result = result.next my_list1 = LinkedList([125,115,95,35,8,6]) my_list2 = LinkedList([135,125,105,95,37,17,8,5]) my_list1.find_max_sum_list(my_list1.head, my_list2.head)
입력
[125,115,95,35,8,6], [135,125,105,95,37,17,8,5]
출력
6 8 17 37 95 115 125 135