Leetcode 876. Middle of the Linked List
Problem Description
For this problem, we are given a non-empty, singly linked list like [1,2,3,4,5] with a head node 'head'. The objective is to return a middle node from this linked list. However, if there are two middle nodes, we need to return the second middle node instead.
Let's consider an example to make this concept clear.
If our input linked list is [1,2,3,4,5], the middle node value is 3.
If our input linked list is [1,2,3,4,5,6], we have two middle node values 3 and 4. Hence, we return the second one i.e.,4.
Approach of Solution
The approach we are considering here for solution is of Two Pointers. We initialize two pointers, one slow and one fast both at the head of the linked list. The slow pointer moves one step at a time while the fast pointer moves two steps at a time. By the time the fast pointer reaches the end of the linked list, the slow pointer would be at the middle of the list.
The ascii illustration for the approach would look like this for the example given above:
1 2 3Input: [1,2,3,4,5,6] 4 |_fast 5 --->slow 6 7After a few iterations, we get 8Input: [1,2,3,4,5,6] 9 |_fast 10 --->slow 11 12Here, the slow pointer is at the value at node 4 which is exactly the middle of the list.
Solution
Python
1 2python 3# Definition for singly-linked list. 4# class ListNode: 5# def __init__(self, x): 6# self.val = x 7# self.next = None 8 9class Solution: 10 def middleNode(self, head: ListNode) -> ListNode: 11 slow = head #initialize slow pointer 12 fast = head #initialize fast pointer 13 14 while fast and fast.next: #iterate until end of list 15 slow = slow.next #slow pointer moves one step 16 fast = fast.next.next #fast pointer moves two steps 17 18 return slow #return slow pointer which is at middle of list
Java
1
2java
3// Definition for singly-linked list.
4// public class ListNode {
5// int val;
6// ListNode next;
7// ListNode() {}
8// ListNode(int val) { this.val = val; }
9// ListNode(int val, ListNode next) { this.val = val; this.next = next; }
10// }
11
12class Solution {
13 public ListNode middleNode(ListNode head) {
14 ListNode slow = head; //initialize slow pointer
15 ListNode fast = head; //initialize fast pointer
16
17 while (fast != null && fast.next != null) { //iterate until end of list
18 slow = slow.next; //slow pointer moves one step
19 fast = fast.next.next; //fast pointer moves two steps
20 }
21
22 return slow; //return slow pointer which is at middle of list
23 }
24}
JavaScript
1
2javaScript
3// Definition for singly-linked list.
4// function ListNode(val, next) {
5// this.val = (val===undefined ? 0 : val)
6// this.next = (next===undefined ? null : next)
7// }
8
9function middleNode(head) {
10 let slow = head; //initialize slow pointer
11 let fast = head; //initialize fast pointer
12
13 while (fast && fast.next) { //iterate until end of list
14 slow = slow.next; //slow pointer moves one step
15 fast = fast.next.next; //fast pointer moves two steps
16 }
17
18 return slow; //return slow pointer which is at middle of list
19};
C++
1
2C++
3// Definition for singly-linked list.
4// struct ListNode {
5// int val;
6// ListNode *next;
7// ListNode() : val(0), next(nullptr) {}
8// ListNode(int x) : val(x), next(nullptr) {}
9// ListNode(int x, ListNode *next) : val(x), next(next) {}
10// };
11
12class Solution {
13public:
14 ListNode* middleNode(ListNode* head) {
15 ListNode* slow = head; //initialize slow pointer
16 ListNode* fast = head; //initialize fast pointer
17
18 while (fast && fast->next) { //iterate until end of list
19 slow = slow->next; //slow pointer moves one step
20 fast = fast->next->next; //fast pointer moves two steps
21 }
22
23 return slow; //return slow pointer which is at middle of list
24 }
25};
C#
1
2C#
3// Definition for singly-linked list.
4// public class ListNode {
5// public int val;
6// public ListNode next;
7// public ListNode(int val=0, ListNode next=null) {
8// this.val = val;
9// this.next = next;
10// }
11// }
12
13public class Solution {
14 public ListNode MiddleNode(ListNode head) {
15 ListNode slow = head; //initialize slow pointer
16 ListNode fast = head; //initialize fast pointer
17
18 while (fast != null && fast.next != null) { //iterate until end of list
19 slow = slow.next; //slow pointer moves one step
20 fast = fast.next.next; //fast pointer moves two steps
21 }
22
23 return slow; //return slow pointer which is at middle of list
24 }
25}
The inclusion of all these solutions ensures that developers proficient in different languages can approach this problem. The two pointer method is versatile and can be applied in similar areas e.g., reversing a linked list, finding the nth node from the end etc. This approach maintains a constant space complexity of O(1), since we only ever use two pointers. The time complexity is O(N) because we have to traverse the list to reach its end with the fast pointer. Thus, this method is both space-efficient and reasonably fast.
In conclusion, exploring such algorithms not only improves our problem-solving skills but also deepens our understanding of the building blocks of data structures. This in turn helps us to write more efficient and effective software. It shows that sometimes, an efficient solution may not involve complex structures or advanced techniques, but rather a smart and simple approach like using two pointers. This serves as a reminder that there is an art to simplifying problems and solutions in computer programming, and developing this art requires time, practice, and an open mind that is ready to learn and adapt.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.