[항해99] LinkedList

Linked List

Linked List란 ?

각 노드간 연결된 형태로 표현하는 자료구조

그러면 Array List랑 차이는 뭔데?

ArrayList :

• 자료의 접근은 쉬움. 예를들어 4번째에 있는 값을 가져와! 라고 할 때 파이썬의 경우 lst[3] 를 하면 바로 4번째 값을 받을 수 있다.
• 자료를 삽입할 때는 어렵다.예를 들어 리스트의 3번째에 4라는 값을 넣어줘! 라고 하면, 기존의 배열에서 3번째부터 끝까지 모든 배열을 한 칸씩 뒤로 밀어준 다음 빈 공간이 3번째에 생기면 거기 쏙 넣어야 해서 어렵다.

Linked List :

• 자료의 접근이 어려움. 4번째에 있는 값을 가져와! 라고 할 때, 첫 노드 head에서부터 한 칸씩 뒤로. 뒤로. 뒤로 해야 4번째에 있는 값을 받을 수 있다.
• 자료를 삽입하기는 쉽다. 3번째에 4라는 값을 넣어주려면, 2번째의 next를 4라는 값을가진 노드랑 이어주고, 이 노드의 뒤에 3의 next를 이어주면 됨!

문제

실제로 알고리즘 문제에서 Linked List를 직접 활용하는 문제가 나오진 않는다고 한다. 이걸 이용해서 해결의 실마리를 잡을 순 있어도. 그냥 "기본" 이라는 것이다.

배열 뒤집기

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

Reverse Linked List - LeetCode

말 그대로 LinkedList 배열을 뒤집는 코드이다.
두가지 방법이 있는데, 나는 재귀호출방식으로 코드를 작성했다.

참고로 파이썬의 경우 동적 언어라서 함수 인자를 마음대로 받아도 괜찮은데, 이상한 값이 들어가서 생기는 오류를 방지하기 위해서? 인자와 리턴의 타입을 정해주는 경우도 있다고 한다 .

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

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

리스트 합치기

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

Merge Two Sorted Lists - LeetCode

두 배열을 합치는 코드다.

# Definition for singly-linked list.
from typing import Optional


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


class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        new_l= dummy = ListNode()
        while (list1 and list2):
            if list1.val < list2.val:
                new_l.next = list1
                list1 ,new_l = list1.next, list1
            else:
                new_l.next = list2
                list2, new_l = list2.next, list2
        
        if list1 or list2:  # 둘 중 하나는 남아있을거니까.
            new_l.next = list1 if list1 else list2
        return dummy.next

 

여기서 좀 재밌었던 게, 일반적으로 LinkedList라고 내가 배워왔던 것은 Head를 가지고, Node라는 객체를 줄줄이 이어서 가지고 있는 LinkedList객체를 배웠는데, 여기서는 ListNode만을 활용해서 문제를 해결했다. 

 

그리고 두번째 트릭은 new_l로 리스트순회를 같이도는 포인터 하나, dummy로 리스트의 맨처음을 나타내는 포인터 하나를 두어서 (사실 포인터가 아니라 노드긴 한데, 의미상 포인터라고 했습니다) 양 리스트를 순회할 때는 new_l로 순회하고 마지막에 리턴할 때는 맨처음 노드(dummy)의 바로 다음 노드 ( 얘부터 list1 or list2의 값이 들어가니까.)를 리턴했음.

홀수 짝수 배열

https://leetcode.com/problems/odd-even-linked-list/

Odd Even Linked List - LeetCode

 

홀수번째와 짝수번째 노드를 각각 분리해서 짝수번째를 뒤로 보내라 라는 코드입니다. 

 

이거도 똑같이 포인터를 두개를 잡고 먼저 정렬한 다음에 짝수 처음을 홀수 끝에 붙이면 되는 문제였네요.

# Definition for singly-linked list.
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        odd = head
        evenHead = even = head.next

        while even and even.next:
            odd.next = odd.next.next
            odd = odd.next

            even.next = even.next.next
            even = even.next

        odd.next = evenHead

        return head