876. Middle of the Linked List

Middle of the Linked List - LeetCode

링크드 리스트의 중간 값을 들고오는 문제이다.

• 한바퀴 돌면서 size 를 알고 중간 index까지 한번더 순회
• extra array 저장해서 count/2

둘다 딱히 정답같은 느낌은 아니다.

주먹구구 구현

class Solution {
    func middleNode(_ head: ListNode?) -> ListNode? {
        var curr = head
        var arr : [ListNode] = []
        
        while curr!.next != nil {
            arr.append(curr!)
            curr = curr!.next
        }
        arr.append(curr!)
        return arr[arr.count/2]
    }
}

Fast pointer slow pointer

www.geeksforgeeks.org/how-does-floyds-slow-and-fast-pointers-approach-work/

How does Floyd's slow and fast pointers approach work? - GeeksforGeeks

2칸씩 가는 fast 포인터와 한칸씩 가는 slow 포인터를 사용한다.

fast pointer 가 tail 에 도달했다면 속도가 1/2인 slow 포인터는 LinkedList 의 중간에 위치할 것 이다.

class Solution {
    func middleNode(_ head: ListNode?) -> ListNode? {
        var fast = head
        var slow = head
        while fast != nil && fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
        }
        return slow
    }
}