[LeetCode] #876 Middle of the Linked List (repeat:0)

 

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. 

 

 

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

Middle of the Linked List - LeetCode