[leetcode 876] Middle of the Linked List

876. Middle of the Linked List

https://leetcode.com/problems/middle-of-the-linked-list/

해결 과정

느린 포인터와 빠른 포인터 2개를 사용한다.

빠른 포인터가 null (짝수 케이스) 또는 빠른 포인터.next 가 null (홀수 케이스) 일때까지, 빠른 포인터는 느린 포인터에 2배씩 이동한다.

[sample]

• 짝수 케이스: [1,2,3,4] -> [3,4]
• 홀수 케이스: [1,2,3,4,5] -> [3,4,5]

코드

fun middleNode(head: ListNode?): ListNode? {
    var slow = head
    var fast = head

    while(fast!= null && fast.next!=null) {
        slow = slow?.next
        fast = fast?.next?.next
    }
    
    return slow
}

배운 점

• 홀수/짝수 케이스를 나누어 생각
• 1/N 지점의 linked list 도 비슷하게 구현 가능할 것이다.