[Coding] LinkedLists, Listnode

Leetcode를 풀다가 처음 알게된 개념(?).. 유명하고 중요한 개념이라고 하는데 알고리즘이나 코딩을 제대로 배워본 적이 없는 나에게는 넘 생소한 개념이였다. 그래서 이왕 알게된 겸, 블로그에 정리하면서 공부해봄. 

 

Merge two sorted lists

You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.

여기서 linked list가 주어진다. 말 그대로 리스트 안의 값들이 서로 연결되어 있는 형태의 리스트이고, 이때 연결은 포인터로 이뤄진다.

ListNode Example:
[value|next] -> [value|next] -> [value|next] -> null

[1|→] -> [2|→] -> [3|→] -> null

 

그리고 아래와 같은 클래스 형식으로 주로 정의되는데, 이때 next에 해당하는 포인터를 조정해서 리스트를 재정렬할 수 있다. 

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val    # The value stored in this node
        self.next = next  # Reference to the next node

 

나는 문제에서 리스트가 이렇게 주어졌길래 리스트의 값들을 직접 노드에 넣고 포인터도 할당해야하나 싶었는데, 그냥 알아서 된다고 한다.

list1 = [1,2,4]  # This is just for showing the values
list2 = [1,3,4]  # This is just for showing the values

# list1 would already be:
# ListNode(1) -> ListNode(2) -> ListNode(4)

# list2 would already be:
# ListNode(1) -> ListNode(3) -> ListNode(4)

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    # list1 is already the head (first node) of the first linked list
    # list2 is already the head (first node) of the second linked list
    
    # You can access values like:
    # list1.val  # gives you the first value
    # list1.next.val  # gives you the second value
    # list1.next.next.val  # gives you the third value

리스트에 50개까지 들어간다고 했는데, 그러면 값을 저렇게 .next.next로 호출하는 게 말이 되나? 싶었다.

 

이렇게 하면 길이 상관없이 끝노드까지 갈 수 있다고. 

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    # Example of how to traverse a linked list
    current = list1  # Start at the head
    while current is not None:  # Keep going until we hit the end
        print(current.val)  # Do something with the current value
        current = current.next  # Move to next node

 

여기서 또 하나 주의점! head가 있다. 

current = list1 #start at the head 이 줄에 보면 헤드가 있는데 노드에서는 헤드가 중요한 개념인 것 같다.

헤드는 링크드 리스트의 첫 번째 노드를 가르킨다. 즉, 처음 시작점을 의미한다. 

list1 = [1, 2, 4] 가 주어졌을 때 헤드는 1이다. 이렇게 헤드가 1을 가르키면, 다른 리스트의 값과 비교한 뒤에 헤드를 옮겨서, 다음 2를 가르키고, 그런 느낌. 값 자체가 아니고, 위치 정보를 나타내는 포인터 같은 느낌.

list2 = [1, 3, 4]와 합쳐서 순서를 내림차순 정렬을 시킨다면,

빈 더미 리스트를 만들고, list1의 값과 list2의 값을 비교해서 작은 숫자를 더미 리스트에 추가한다.

리스트 둘 중에 하나가 없는 경우나, 한쪽이 먼저 끝나는 경우에 대한 예외 사항도 처리해준다. 

# Definition for singly-linked list

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
        
def mergeTwoLists(self, list1: Optional[ListNode], list2:Optional[ListNode]) -> Optional[ListNode]:
    if not list1:
        return list2
    if not list2:
        return list1
    
    dummy = ListNode(0)
    current = dummy
    
    while list1 and list2:
        if list1.val <= list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next
    
    if list1:
        current.next = list1
    if list2:
        current.next = list2
    
    return dummy.next