Find the middle node of the linked list

Given a singly linked list, the task is to find the middle node of the list. If the list has an even number of nodes, return the second middle node.

Input-Output Examples

Example 1:

  • Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
  • Output: 3 (The middle node is 3)

Example 2:

  • Input: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> NULL
  • Output: 40 (The list has an even number of nodes, so the second middle node is 40)

Example 3:

  • Input: 1 -> 2 -> NULL
  • Output: 2 (The list has an even number of nodes, so the second middle node is 2)

Example 4:

  • Input: NULL
  • Output: NULL (The list is empty)

Approach:
Technique to be used: Two-pointer technique (slow and fast pointers)

To find the middle of a linked list, we can use the two-pointer technique, also known as the slow and fast pointer approach. This method ensures that we find the middle node in a single pass through the list.

Steps to implement:

  1. Initialize two pointers, slow and fast, both pointing to the head of the list.
  2. Move slow one step at a time, and fast two steps at a time.
  3. When fast reaches the end of the list, slow will be at the middle node.

C++ Program to find the middle node of the linked list

cpp
#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* findMiddle(ListNode* head) {
        if (!head) return NULL;
        
        ListNode* slow = head;
        ListNode* fast = head;
        
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        return slow;
    }
};

// Helper function to print the linked list
void printList(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main() {
    // Creating a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    Solution sol;
    ListNode* middle = sol.findMiddle(head);

    // Printing the middle of the linked list
    if (middle) {
        cout << "The middle node is: " << middle->val << endl;
    } else {
        cout << "The list is empty." << endl;
    }

    return 0;
}

Java Program to find the middle node of the linked list

java
// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Solution {
    public ListNode findMiddle(ListNode head) {
        if (head == null) return null;
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
    
    // Helper function to print the linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        // Creating a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        Solution sol = new Solution();
        ListNode middle = sol.findMiddle(head);

        // Printing the middle of the linked list
        if (middle != null) {
            System.out.println("The middle node is: " + middle.val);
        } else {
            System.out.println("The list is empty.");
        }
    }
}

Python Program to find the middle node of the linked list

python
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def find_middle(self, head: ListNode) -> ListNode:
        if not head:
            return None
        
        slow, fast = head, head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        return slow

# Helper function to print the linked list
def print_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("NULL")

# Creating a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

sol = Solution()
middle = sol.find_middle(head)

# Printing the middle of the linked list
if middle:
    print("The middle node is:", middle.val)
else:
    print("The list is empty.")

Finding the middle of a linked list can be efficiently achieved using the two-pointer technique, which involves moving one pointer at half the speed of the other. This approach ensures a linear time complexity of O(n), where n is the number of nodes in the list.

DSA

7904

533

Related Articles