ⓛⓔⓔⓣ ⓜⓔ ⓒⓞⓓⓔ!
https://leetcode.com/problems/middle-of-the-linked-list/
Middle of the Linked List - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
876. Middle of the Linked List
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
Example 1:
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.
Example 2:
Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.
Constraints:
- The number of nodes in the list is in the range [1, 100].
- 1 <= Node.val <= 100
문제 정리
single linked list에서 중간 노드를 반환하는 문제(중간 노드가 두 개라면 두 번째 노드 선택)
생각의 흐름
처음부터 끝까지 가면서 노드 수를 세고, 중간 노드를 찾을 수도 있겠지만
fast pointer를 사용하면 한 번에 중간 노드 찾기 가능한..
한 번에 한 칸씩 이동하는 느린 포인터(slow)와 한 번에 두 칸씩 이동하는 빠른 포인터(fast)가 함께 이동한다.
fast pointer가 리스트의 끝에 도달하면 slow pointer는 딱 절반까지 이동하게된다.
Solution Code
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};