내일은 알고리즘

https://leetcode.com/problems/reverse-linked-list/

LinkedList를 뒤집는 문제입니다.

재귀함수를 이용해 리스트를 타고 끝을 찾은 뒤 끝에서부터 재귀함수를 빠져나오면서 연결 방향을 거꾸로 뒤집었습니다.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if(not head or not head.next):
            return head
        
        rest = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return rest

input = ListNode(1,ListNode(2, ListNode(3,ListNode(4, ListNode(5,None)))))
# input = None

answer = Solution().reverseList(input)
while(answer):
    print(answer.val)
    answer = answer.next

https://leetcode.com/problems/merge-two-sorted-lists/

구현은 어렵지 않지만 LinkedList에 낯설면 접근하기 어려울 수도 있는 문제입니다.

두개의 정렬된 LinkedList가 주어지는데 이 둘을 합쳐 정렬된 하나의 LinkedList를 만들어야 합니다.

결과를 저장하기 위한 새로운 하나의 리스트를 만들고 입력된 두개의 리스트를 비교하면서 작은 순서대로 새로운 리스트에 붙여나갔습니다.

만약 입력 리스트 중에 하나가 끝난다면 결과 리스트의 맨 끝이 남은 입력리스트를 가리키게 하고 리턴했습니다.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        root = ListNode()
        index = root
        
        while(list1 and list2):
            if(list1.val > list2.val):
                index.next = list2
                list2 = list2.next
                index = index.next
            else:
                index.next = list1
                list1 = list1.next
                index = index.next
        
        if(list1):
            index.next = list1
        elif(list2):
            index.next = list2
        
        return root.next
    

input = [[ListNode(1,ListNode(2, ListNode(4,None))),ListNode(1,ListNode(3, ListNode(4,None)))],
         [None,None],
         [None,ListNode(1,ListNode(3, ListNode(4,None)))],
         [ListNode(1,None),None]]

for i in input:
    answer = Solution().mergeTwoLists(i[0],i[1])
    while(answer):
        print(answer.val)
        answer = answer.next