Find Middle of Linked List

105.2k
0

Given head of a singly linked list, return data value present at middle node. For an even number of nodes, return data value from second middle node.

A linked list contains at least one node. Node data can be any valid integer.

Example 1

Input: head = [1, 2, 3, 4, 5]

Output: 3

Explanation: Linked list length equals 5, so middle position equals 3.

Example 2

Input: head = [1, 2, 3, 4, 5, 6]

Output: 4

Explanation: Linked list length equals 6. Two central positions are 3 and 4, so second middle value equals 4.

Approach 1

In this approach, we first count the total number of nodes in the linked list. Once the length is known, the middle node can be found by moving length / 2 steps from the head.

For an odd-length linked list, this reaches the unique middle node. For an even-length linked list, integer division naturally points to the second middle node, which matches the required output.

Algorithm

  • Traverse the linked list once to count the total number of nodes, as the middle position depends on the list length.

  • Compute the middle position as count / 2, since integer division gives the required middle index for both even and odd-sized lists.

  • Reset the traversal pointer to head, as the second traversal needs to begin from the start of the list.

  • Move the pointer count / 2 steps forward, which places it at the middle node according to the required indexing.

  • Return the data stored in the current node, as the pointer now represents the middle element of the linked list.

Dry Run

middle of a ll

middle of a ll

Solution

#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int data;
ListNode* next;
// Constructor for a linked list node
ListNode(int value) : data(value), next(nullptr) {}
};
class Solution {
public:
// Function to find middle node data using node counting
int findMiddle(ListNode* head) {
if(!head) return -1;
// Count total nodes in linked list
int count = 0;
ListNode* temp = head;
while (temp != nullptr) {
count++;
temp = temp->next;
}
// Move to second middle position for even length
int middleIndex = count / 2;
temp = head;
while (middleIndex > 0) {
temp = temp->next;
middleIndex--;
}
// Return middle node data
return temp->data;
}
};
// Function to build linked list from values
ListNode* buildList(vector<int>& values) {
ListNode* head = new ListNode(values[0]);
ListNode* tail = head;
for (int i = 1; i < (int)values.size(); i++) {
tail->next = new ListNode(values[i]);
tail = tail->next;
}
return head;
}
// Driver code
int main() {
vector<int> values = {1, 2, 3, 4, 5, 6};
ListNode* head = buildList(values);
Solution sol;
cout << sol.findMiddle(head) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), linked list traversal occurs twice across N nodes.

Space Complexity: O(1), only constant extra pointer and counter variables are used.

Approach 2

The slow and fast pointer technique finds the middle of a linked list in a single traversal. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. When the fast pointer reaches the end of the list, the slow pointer is positioned at the middle node. For even-length linked lists, this method naturally returns the second middle node.

Algorithm

  • Initialize two pointers, slow and fast, at head, where slow moves one step at a time and fast moves twice as fast.

  • Traverse while fast and fast->next are not NULL, as this allows fast to reach the end while slow moves toward the middle.

  • Move slow one step and fast two steps in each iteration, so when fast reaches the end, slow has reached the middle position.

  • Return the data stored in slow, as it now represents the middle node of the linked list.

Dry Run

find middle of ll slow fast

find middle of ll slow fast

Solution

#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int data;
ListNode* next;
// Constructor for a linked list node
ListNode(int value) : data(value), next(nullptr) {}
};
class Solution {
public:
// Function to find middle node data using two pointers
int findMiddle(ListNode* head) {
// Move fast pointer two steps and slow pointer one step
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
// Return middle node data
return slow->data;
}
};
// Function to build linked list from values
ListNode* buildList(vector<int>& values) {
ListNode* head = new ListNode(values[0]);
ListNode* tail = head;
for (int i = 1; i < (int)values.size(); i++) {
tail->next = new ListNode(values[i]);
tail = tail->next;
}
return head;
}
// Driver code
int main() {
vector<int> values = {1, 2, 3, 4, 5, 6};
ListNode* head = buildList(values);
Solution sol;
cout << sol.findMiddle(head) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), linked list traversal visits at most N nodes through pointer movement.

Space Complexity: O(1), only two extra pointers are used.

Interview follow-up Questions

Second middle node is returned for even length. For [1, 2, 3, 4, 5, 6], answer equals 4.

Linked List

Read Similar Blogs

Linked List

Swap Nodes in Pairs

Given the head of a singly linked list, swap every two adjacent nodes and return the modified head. Node values must stay inside the original nodes, so the task swaps node links instead of rewritin...

59.9k
Linked List

Merge Two Sorted Linked Lists

Given heads of two sorted linked lists, merge both lists into one sorted linked list and return the head of the merged list. Every node stores an integer value and a pointer to the ne...

114.6k
Linked List

Find pairs with given sum in Doubly Linked List

Given a sorted doubly linked list containing positive distinct integers and an integer target, find every pair of node values whose sum equals target. Return pairs in increasing order based on the...

101.5k
Comments0