[leetcode] 876. Middle of the Linked List

문제

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

 

Example 1:

.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

Note: The number of nodes in the given list will be between 1 and 100.

 

---

풀이

단일 링크드 리스트의 중간 노드를 찾는 문제, circular linked list의 순환여부를 검사하는 문제와 같이 Floyd's cycle-finding algorithm을 이용해서 풀면 된다.

1.  시작노드를 가리키는 두개의 포인터를 준비한다.
2.  하나의 포인터는 한번에 두 노드씩, 다른 하나는 한번에 한 노드씩 이동한다.
3.  단일 링크드 리스트이므로 2칸 씩 이동하는 포인터가 null를 만날때 다른 하나의 포인터가 중간에 위치한다.

 

---

코드

class Solution {
    public ListNode middleNode(ListNode head) {
        var fastRunner = head;
        var slowRunner = head;

        while(fastRunner != null && fastRunner.next != null){
            fastRunner = fastRunner.next.next;
            slowRunner = slowRunner.next;
        }

        return slowRunner;
    }
}

---

참고

• 876. Middle of the Linked List
• Floyd's cycle-finding algorithm