LinkedList의 중간 노드를 찾는 문제인데 미국 신입개발자들 인터뷰에 많이 나온 문제라고 한다. 플로이드의 토끼와 거북이(Floyd Tortoise and Hare) 알고리즘으로 풀었다.
# Description
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]
# Solution
class Solution{
public ListNode middleNode(ListNode head){
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
# Explanation
This method uses two pointers, slow and fast. They both are initialized with head of the LinkedList. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. By the time when fast pointer reaches at the end of the LinkedList, the slow pointer will be at the middle of the LinkedList
# Example of Even number of Nodes
Initially
slow = Node 1, fast = Node 1
Here, I initialized two pointers to the head of the LinkedList. Therefore two pointers point to the Node1.
First Iteration
slow = Node2 , fast= Node3
slow moves one node at a time, therefore, points to the Node2, and fast moves two nodes at a time, therefore points to the Node3
Second Iteration
Now, I have to consider the while loop condition. fast is not null (it's Node3). fast.next is also not null(it's Node4).
So it goes to loop again
slow = slow.next -> slow = Node3
fast = fast.next.next -> fast = null
Since fast reached the null, the while loop will stop. The method resturns slow, which is pointing to the Node3.
Result
Time Complexity : O(n)
- two pointers iterates though the linked list using a while loop, and it stops until the fast node reaches to the end of the linked list. The 'n' represents the number of nodes in the list
Space Complexity : O(1)
- The code uses only a constant number of variables ('slow' and 'fast' pointers), and does not require additional memory proportional to the size of the input.
'Programming > LeetCode' 카테고리의 다른 글
[LeetCode] #1290 Convert Binary Number in a Linked List to Integer (repeat : 0) (0) | 2024.01.12 |
---|---|
[LeetCode] #83 Remove Duplicates from Sorted List (repeat : 0) (0) | 2024.01.11 |
[LeetCode] #86 partition List (repeat : 0 ) (0) | 2024.01.07 |
[LeetCode] #9 Remove Nth Node From End of List (repeat:0) (1) | 2023.12.31 |
[LeetCode] #141 Linked List Cycle (repeat:1) (0) | 2023.12.25 |