linked list 다루는 연습 - 가운데 노드 찾기

(1) 처음에 풀어 본 방식

: 노드를 지날 때마다 카운트를 세서 defaultdict에다가 넣어두자. 나중에 가운데 인덱스 값을 키로 갖는 딕셔너리 값을 가져오면 되겠다.

## linked list의 가운데 노드 찾기. (확인을 위해 val을 출력)
## + 짝수개일 경우, 절반으로 갈랐을 때 우측 노드를 찾기.

head1 = createList([1, 2, 3, 4, 5, 6])

def pickMiddleNode(head: ListNode):
    if not head:
        return None
    else:
        node = head
        dict = collections.defaultdict(ListNode)  # 몇 번째에 어떤 노드가 있었는지 기록하는 dict.
        count = 0
        while node:
            count += 1
            dict[count] = node  # count 는 노드의 자리 인덱스(1부터 시작하긴 했지만.) 
            node = node.next  
        target_index = count // 2 + 1  # 정 가운데 인덱스는 자료 개수를 2로 나눈 몫에 1을 더하면 된다.
        target_node = dict[target_index]  # 타겟 노드를 dict 로부터 찾아온다.
        return target_node.val  # 타겟 노드의 값을 반환

print(pickMiddleNode(head1))

(2) 다른 방식

:또 다르게는, 앞에서 배웠던 runner 방식이 가능하다. 정석대로 한 칸씩 움직이는 포인터(slow runner) 뿐만 아니라, 두배 빨리 움직이는 포인터(fast runner)를 작동시킨다. 그 친구가 끝에 다다르면 우리는 그 시점을 표지로 삼을 수 있다. 

head1 = createList([1, 2, 3, 4, 5, 6, 7, 8])
head2 = createList([1, 2, 3, 4, 5, 6, 7, 8, 9])

def pickMiddleByRunner(head: ListNode):
    if not head:
        return None
    else:
        slow_node = head
        fast_node = head

        while slow_node:
            slow_node = slow_node.next
            fast_node = fast_node.next.next
            if fast_node and not fast_node.next:  # 홀수번째 칸만 도착하는 fast runner 가 어떤 값에 도착했지만 다음자리는 없다면 > 홀수개
                return slow_node.val
            if fast_node.next and not fast_node.next.next:  # .. fast runner 가 다음 값은 있지만 그 다음은 없다면 > 짝수개
                return slow_node.next.val

print(pickMiddleByRunner(head1))  #### >>> 5
print(pickMiddleByRunner(head2))  #### >>> 5

(3) 마찬가지로 runner 기법이지만, 코드없는 프로그래밍 유튜버님(?)의 코드는 아래와 같았다. 역시.. 내 시도보다 훨씬 더 간결하다. 대단..!!

  def fastSlow(self, head:ListNode) -> ListNode:
    slow_node = head
    fast_node = head
    
    while fast_node:
      if fast_node.next:
        slow_node = slow_node.next
        fast_node = fast_node.next.next
      else:
        break
        
    return slow_node