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.