“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/merge-two-sorted-lists/submissions/
당분간 연결 리스트를 이용한 문제다. 오늘은 정렬된 연결 리스트다.
class Solution:
def mergeTwoLists1(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
if not l1 or (l2 and l1.val > l2.val):
l1, l2 = l2, l1
if l1:
l1.next = self.mergeTwoLists1(l1.next, l2)
return l1
def mergeTwoLists2(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
lst1: List = self.convertToList(l1)
lst2: List = self.convertToList(l2)
concated = lst1 + lst2
concated.sort()
return self.createListNode(concated, 0)
def convertToList(self, ln: ListNode):
lst = []
node = ln
while node:
lst.append(node.val)
node = node.next
return lst
def createListNode(self, lst: List, index: int) -> ListNode:
if not lst:
return None
if index + 1 >= len(lst):
return ListNode(lst[index])
else:
return ListNode(lst[index], self.createListNode(lst, index + 1))주어진 두 연결 리스트를 병합하되 정렬된 상태로 반환해야한다. 순간 그냥 리스트를 생각해서 왜 쉽지?라고 착각을 해버렸다. 그런데 리트코드 문제상에서 제약이 없다면 지난번처럼 연결 리스트를 파이썬 리스트로 바꿔서 + 연산해서 정렬한 결과를 연결 리스트로 만들어서 반환하는 것도 방법이겠다 싶어서 그렇게 했더니 에러 없이 통과돼서 난감했다. 그 코드가 mergeTwoList2()이다.
책에서 한 풀이는 mergeTwoList1()인데, 코드가 짧고 재귀로 되어 있어서 도통 이해가 안 된다. 연결 리스트 변화 과정을 따라 그려가면서 읽어도 대충 뭘 하는지는 알겠는데 마음으로 와닿지 않는 느낌?
아니면 내가 어렵게 접근해서 그럴 수도 있다. 그냥 두 연결 리스트의 노드를 각각 비교하는데, 스왑을 통해 작은 수를 한쪽 연결 리스트에 넣고 if not l1 or (l2 and l1.val > l2.val): l1, l2 = l2, l1 그 연결 리스트 노드의 넥스트에 넥스트 노드와 다른쪽을 비교해서 나온 결과를 할당하는 방식 l1.next = self.mergeTwoLists1(l1.next, l2) 으로 반복한다. …내가 적었지만 무슨 말인지 역시 모르겠다.
그냥 각각의 노드를 비교해서 작은 노드를 한쪽에 몰아넣는 방식인듯. 노드의 넥스트 노드가 자꾸 헷갈려서 문제지… 이번 문제는 다음에 다시 봐도 이해가 잘 안 될 것 같다.