복습하기2

역순연결리스트, 두 정렬 리스트의 병합, 홀짝 연결 리스트

03/13/2022

오늘의 하이라이트는 연결리스트를 이해하는것이다.
그림에 나온것중 밑에 있는것이 연결리스트 (Linked list)라고 부르는 것이다. 이것을 이해하기 위해서 노드, 화살표, 포인터, 헤드 그리고 테일에 대해서 알면 좋은것 같다.
Node: 네모난것 그자체. 노드 안에는 next와 데이터값(value)가 들어있다.
Pointer: 각 노드에서 다음 포인터 값을 가르키는것 (?)이라고 한다.
Head: 이것은 가장 처음에 시작되는 노드를 가르킨다.
Tail: 이것은 가장 마지막에 오는 노드를 가르킨다. Next는 none을 가르키고 있다.

연결리스트는 한쪽 방향으로만 흐른다. 한쪽으로만...왜그런걸까? 수많은 블로그와 수많은 글들을 보고, 그리고 파이참에 돌아와서 느낀거지만 이것은 추상적인 개념과 보이지않는 데이터들이 왔다갔다하는 것들의 결합이랄까? 우리가 코드를 돌리면 위에서 아래로 읽고 변수에 무엇이 저장되고 for문에 어떻게 들어가서 결과값이 나오는지를 한다. 한쪽방향으로 흐르는 것을 볼수있다. 아마도 그런 것이 아닐까? 여기서 제일 중요한 포인트는 화살표 방향이다. 이따가 역순 연결 리스트 문제에서 볼수있지만, 화살표의 방향만을 바꾸어 시퀀스를 거꾸로 돌릴수가 있다. 기가막힌다. 하루종일 이해하려고 노력했다. 머리는 알지만 마음은 모르는(?) 그런 현상도 겪고 참 아리송했다.

사실 어레이리스트로 저장도 가능한데 굳이 왜 화살표 써주면서 이런생각을 왜하는 것일까?

남병관 튜터님이 말씀해주신 것이다!
숙지해야한다!

쉽게말해서, 연결리스트라는 것은 화살표 방향의 흐름이다. 화살표가 어디를 가르키고, 변수의 초기화가 진행됨에 따라 데이터의 공기와 흐름이 달라진다. 이것이 메인 포인트다.

연결리스트 구현된것:

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


class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, val):
        if not self.head:
            self.head = ListNode(val, None)
            return

        node = self.head
        while node.next:
            node = node.next

        node.next = ListNode(val, None)

node.next: 화살표
node: 노드 그자체
처음에는 항상 노드와 화살표가 없는 상태로 시작한다. 그리고 난 후에 노드가 다음 노드를 가르키는 인풋이 오면 반복문으로 돌려서 끝에 값이 아무것도 없는 상태, 즉 화살표가 아무것도 아닌것을 가르킬때까지 반복하고 마지막에 온 것을 리턴한다.
굉장히 중요한 것고 많이 응용가능하므로 반드시 알아야하는 부분이라고 한다.

역순연결리스트

바로 응용!
이 문제는 오늘 나의 발표부분이였다. 발표가 아니였다면 이해하기 어려웠을것이다.

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        node, prev = head, None
        while node:
            next, node.next = node.next, prev
            prev, node = node, next
        return prev
#이해하려고 팀원이 나에게 알려준 예시.
# None <- 1 2 -> 3 -> 4 -> 5 -> none
# None <- 1 <- 2 3 -> 4 -> 5 -> None
# None <- 1 <- 2 < -3 4 -> 5 -> None
# None <- 1 <- 2 <- 3 <- 4 5 -> None
# None <- 1 <- 2 <- 3 <- 4 <- 5 None   return this part.

두 정렬 리스트의 병합

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if (not l1) or (l2 and l1.val > l2.val):
            l1, l2 = l2, l1
        if l1:
            l1.next = self.mergeTwoLists(l1.next, l2)
        return l1

계속해서 재귀호출하는 방식이다.
여기서 중요한 포인트는 if문에서 흐름의 순서이다.
괄호에서 부터 시작하고, and가 or보다 우선순위가 높다. 신기하다.
그리고 재귀하기위해서 li.next, 즉 화살표는 mergeTwoLists 함수로 넘어간다.

홀짝 연결 리스트

연결리스트를 홀수노드 다음에 짝수노드가 오도록 재구성한다. 공간과 시간복잡도 고려해라~

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        # 예외 처리
        if head is None:
            return None
        odd = head
        even = head.next
        even_head = head.next
        # 반복하면서 홀짝 노드 처리
        while even and even.next:
            odd.next, even.next = odd.next.next, even.next.next
            odd, even = odd.next, even.next
        # 홀수 노드의 마지막을 짝수 헤드로 연결
        odd.next = even_head
        return head

처음에 보자마자 다시 습관이 나와버렸다: 정렬을 하고 각 값을 비교해서 문제조건에맞게 하는것. 하지만 생각이 틀렸다.
여기서 핵심은 처음에 짝수와 홀수를 어떻게 할것인지다. odd = head (처음노드), even = head.next (처음노드의 다음노드 = 짝수), even_head = head.next (짝수노드의 헤드).

알고리즘 공부 쉽지않다....후...할게너무많다