Open In App

Find Middle of the Linked List

Last Updated : 02 Apr, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Given a Singly Linked List, the task is to find the middle of the linked list. If the number of nodes are even, then there would be two middle nodes, so return the second middle node.

Example:

Input: linked list = 1 -> 2 -> 3 -> 4 -> 5
Output: 3 
Explanation: There are 5 nodes in the linked list and there is one middle node whose value is 3.

Input: linked list = 1 -> 2 -> 3 -> 4 -> 5 -> 6
Output: 4 
Explanation: There are 6 nodes in the linked list, so we have two middle nodes: 3 and 4, but we will return the second middle node which is 4.

Find middle of the Linked List using Extra Memory (Brute Force):

Store the entire linked list in a vector or Array List such that each index contains the value of a node. Now, to find the middle of the linked list, we can simply return the value present at the middle of the vector or Array List.

Step-by-step algorithm:

  • Declare a vector(or Array list), say v to store values of all nodes of the linked list.
  • Iterate over the linked list and for each node, push the value of the node in v.
  • After iterating over the entire linked list, find the middle index of the vector, say middleIdx = v.size()/2.
  • Return v[middleIdx] as the middle element of the linked list.

Below is the implementation of the above approach:

C++ 
#include <bits/stdc++.h>
#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
      Node(int x) {
        data = x;
          next = NULL;
    }
};

// Function to add a new node in the beginning of the linked
// list
void pushNode(class Node** head_ref, int data_val)
{

    // Allocate node
    class Node* new_node = new Node(data_val);

    // Link the old list of the new node
    new_node->next = *head_ref;

    // move the head to point to the new node
    *head_ref = new_node;
}

int getMiddle(Node* head)
{
    // vector to store the values of all nodes
    vector<int> v;
    // Traverse through the entire linked list and push all
    // the values into the vector
    while (head != NULL) {
        v.push_back(head->data);
        head = head->next;
    }
    // Find the middle index
    int middleIdx = v.size() / 2;
    // Return the value stored at the middle index
    return v[middleIdx];
}

int main()
{
    Node* head = NULL;
    for (int i = 5; i > 0; i--) {
        pushNode(&head, i);
    }

    cout << "Middle Value Of Linked List is: "
         << getMiddle(head) << endl;
    return 0;
}
Java 
import java.util.Vector;

// Define the Node class for linked list
class Node {
    int data;
    Node next;
      Node(int x) {
        data = x;
          next = null;
    }
}

public class Main {
    // Function to add a new node in the beginning of the
    // linked list
    static void pushNode(Node[] head_ref, int data_val)
    {
        // Allocate node
        Node new_node = new Node(data_val);
        // Link the old list to the new node
        new_node.next = head_ref[0];
        // Move the head to point to the new node
        head_ref[0] = new_node;
    }

    // Function to get the middle value of the linked list
    static int getMiddle(Node head)
    {
        // Vector to store the values of all nodes
        Vector<Integer> v = new Vector<>();
        // Traverse through the entire linked list and push
        // all the values into the vector
        while (head != null) {
            v.add(head.data);
            head = head.next;
        }
        // Find the middle index
        int middleIdx = v.size() / 2;
        // Return the value stored at the middle index
        return v.get(middleIdx);
    }

    public static void main(String[] args)
    {
        // Initialize the head of the linked list
        Node[] head = new Node[1];
        // Push nodes into the linked list in reverse order
        for (int i = 5; i > 0; i--) {
            pushNode(head, i);
        }

        // Print the middle value of the linked list
        System.out.println(
            "Middle Value Of Linked List is : "
            + getMiddle(head[0]));
    }
}
C# 
using System;
using System.Collections.Generic;

// Define the Node class for linked list
public class Node {
    public int data;
    public Node next;
      public Node(int x) {
          data = x;
          next = null;
    }
}

public class MainClass {
    // Function to add a new node in the beginning of the
    // linked list
    static void pushNode(ref Node[] head_ref, int data_val)
    {
        // Allocate node
        Node new_node = new Node(data_val);
        // Link the old list to the new node
        new_node.next = head_ref[0];
        // Move the head to point to the new node
        head_ref[0] = new_node;
    }

    // Function to get the middle value of the linked list
    static int getMiddle(Node head)
    {
        // List to store the values of all nodes
        List<int> list = new List<int>();
        // Traverse through the entire linked list and add
        // all the values to the list
        while (head != null) {
            list.Add(head.data);
            head = head.next;
        }
        // Find the middle index
        int middleIdx = list.Count / 2;
        // Return the value stored at the middle index
        return list[middleIdx];
    }

    public static void Main()
    {
        // Initialize the head of the linked list
        Node[] head = new Node[1];
        // Push nodes into the linked list in reverse order
        for (int i = 5; i > 0; i--) {
            pushNode(ref head, i);
        }

        // Print the middle value of the linked list
        Console.WriteLine(
            "Middle Value Of Linked List is : "
            + getMiddle(head[0]));
    }
}
Javascript 
class Node {
    constructor(x) {
        this.data = x;
        this.next = null;
    }
}

// Function to add a new node in the beginning of the linked list
function pushNode(head_ref, data_val) {
    let new_node = new Node(data_val);
    new_node.next = head_ref[0];
    head_ref[0] = new_node;
}

// Function to get the middle value of the linked list
function getMiddle(head) {
    let v = [];
    // Traverse through the entire linked list and push all the values into the array
    while (head !== null) {
        v.push(head.data);
        head = head.next;
    }
    // Find the middle index
    let middleIdx = Math.floor(v.length / 2);
    // Return the value stored at the middle index
    return v[middleIdx];
}

let head = [null];
// Push nodes into the linked list in reverse order
for (let i = 5; i > 0; i--) {
    pushNode(head, i);
}

// Print the middle value of the linked list
console.log("Middle Value Of Linked List is :", getMiddle(head[0]));
Python3 
class Node:
    def __init__(self, x):
        self.data = x
        self.next = None

# Function to add a new node in the beginning of the linked list


def pushNode(head_ref, data_val):
    new_node = Node(data_val)
    new_node.next = head_ref[0]
    head_ref[0] = new_node

# Function to get the middle value of the linked list


def getMiddle(head):
    v = []
    # Traverse through the entire linked list and push all the values into the list
    while head is not None:
        v.append(head.data)
        head = head.next
    # Find the middle index
    middleIdx = len(v) // 2
    # Return the value stored at the middle index
    return v[middleIdx]


head = [None]
# Push nodes into the linked list in reverse order
for i in range(5, 0, -1):
    pushNode(head, i)

# Print the middle value of the linked list
print("Middle Value Of Linked List is :", getMiddle(head[0]))

Output
Middle Value Of Linked List is: 3

Time Complexity: O(N), where N is the number of nodes in the linked list.
Auxiliary Space: O(N)

Find Middle of the Linked List by Counting Nodes (Two-pass):

Traverse the whole linked list and count the number of nodes. After counting the total number of nodes, again traverse the first (count/2) nodes of the linked list and return the (count/2)th node’s value. This approach traverse the linked list two times to find the middle element of the linked list. 

Step-by-step algorithm:

  • Maintain a function, say getLen(head) that returns the number of nodes in the linked list.
  • Find the number of nodes in the linked list (say len) using the getLen(head) function.
  • Find the middle index midIdx = len/2.
  • Start traversing through the nodes of the linked list and decrement midIdx by 1 for each node.
  • As soon as the midIdx reaches 0, return the current node.

Below is the implementation of the above approach:

C++ 
#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
      Node(int x) {
        data = x;
          next = NULL;
    }
};

// Function to add a new node
void pushNode(Node** head_ref, int data_val)
{

    // Allocate node
    Node* new_node = new Node(data_val);

    // Link the old list of the new node
    new_node->next = *head_ref;

    // move the head to point to the new node
    *head_ref = new_node;
}

/* Utility Function to find length of linked list */
int getLen(Node* head)
{
    int len = 0;
    Node* temp = head;
    // Traverse the entire linked list and increment len by
    // 1 for each node
    while (temp) {
        len++;
        temp = temp->next;
    }
    // Return the number of nodes in the linked list
    return len;
}

int getMiddle(Node* head)
{

    // find length
    int len = getLen(head);
    Node* temp = head;

    // traverse till we reached half of length
    int midIdx = len / 2;
    while (midIdx--) {
        temp = temp->next;
    }
    // temp will be storing middle element
    return temp->data;
}

// Driver Code
int main()
{
    Node* head = NULL;
    for (int i = 5; i > 0; i--) {
        pushNode(&head, i);
    }
    cout << "Middle Value Of Linked List is: "
         << getMiddle(head) << endl;
    return 0;
}
Java 
class Node {
    int data;
    Node next;
      Node(int x) {
        data = x;
          next = null;
    }
}

public class Main {
    // Function to add a new node
    static void pushNode(Node[] head_ref, int data_val)
    {
        // Allocate node
        Node new_node = new Node(data_val);
        // Link the old list of the new node
        new_node.next = head_ref[0];
        // Move the head to point to the new node
        head_ref[0] = new_node;
    }

    // Utility Function to find length of linked list
    static int getLen(Node head)
    {
        int len = 0;
        Node temp = head;
        // Traverse the entire linked list and increment len
        // by 1 for each node
        while (temp != null) {
            len++;
            temp = temp.next;
        }
        // Return the number of nodes in the linked list
        return len;
    }

    // Function to get the middle value of the linked list
    static int getMiddle(Node head)
    {
        // find length
        int len = getLen(head);
        Node temp = head;

        // traverse till we reached half of length
        int midIdx = len / 2;
        while (midIdx > 0) {
            temp = temp.next;
            midIdx--;
        }
        // temp will be storing middle element
        return temp.data;
    }

    // Driver Code
    public static void main(String[] args)
    {
        Node[] head = new Node[1];
        for (int i = 5; i > 0; i--) {
            pushNode(head, i);
        }
        System.out.println(
            "Middle Value Of Linked List is: "
            + getMiddle(head[0]));
    }
}
C# 
using System;

public class Node {
    public int data;
    public Node next;
      public Node(int x) {
        data = x; 
         next = null;
    }
}

public class MainClass {
    // Function to add a new node
    static void pushNode(ref Node head_ref, int data_val)
    {
        // Allocate node
        Node new_node = new Node(data_val);
        // Link the old list of the new node
        new_node.next = head_ref;
        // Move the head to point to the new node
        head_ref = new_node;
    }

    // Utility Function to find length of linked list
    static int getLen(Node head)
    {
        int len = 0;
        Node temp = head;
        // Traverse the entire linked list and increment len
        // by 1 for each node
        while (temp != null) {
            len++;
            temp = temp.next;
        }
        // Return the number of nodes in the linked list
        return len;
    }

    // Function to get the middle value of the linked list
    static int getMiddle(Node head)
    {
        // find length
        int len = getLen(head);
        Node temp = head;

        // traverse till we reached half of length
        int midIdx = len / 2;
        while (midIdx > 0) {
            temp = temp.next;
            midIdx--;
        }
        // temp will be storing middle element
        return temp.data;
    }

    // Driver Code
    public static void Main()
    {
        Node head = null;
        for (int i = 5; i > 0; i--) {
            pushNode(ref head, i);
        }
        Console.WriteLine("Middle Value Of Linked List is: "
                          + getMiddle(head));
    }
}
Javascript 
class Node {
    constructor(x) {
        this.data = x;
        this.next = null;
    }
}

// Function to add a new node
function pushNode(head_ref, data_val) {
    let new_node = new Node(data_val);
    new_node.next = head_ref[0];
    head_ref[0] = new_node;
}

// Utility Function to find length of linked list
function getLen(head) {
    let len = 0;
    let temp = head;
    // Traverse the entire linked list and increment len by 1 for each node
    while (temp) {
        len++;
        temp = temp.next;
    }
    // Return the number of nodes in the linked list
    return len;
}

// Function to get the middle value of the linked list
function getMiddle(head) {
    // find length
    let len = getLen(head);
    let temp = head;

    // traverse till we reach half of length
    let midIdx = Math.floor(len / 2);
    while (midIdx > 0) {
        temp = temp.next;
        midIdx--;
    }
    // temp will be storing middle element
    return temp.data;
}

// Driver Code
let head = [null];
for (let i = 5; i > 0; i--) {
    pushNode(head, i);
}
console.log("Middle Value Of Linked List is: " + getMiddle(head[0]));
Python3 
class Node:
    def __init__(self, x):
        self.data = x
        self.next = None

# Function to add a new node
def pushNode(head_ref, data_val):
    # Allocate node
    new_node = Node(data_val)
    # Link the old list of the new node
    new_node.next = head_ref[0]
    # move the head to point to the new node
    head_ref[0] = new_node

# Utility Function to find length of linked list
def getLen(head):
    len = 0
    temp = head
    # Traverse the entire linked list and increment len by
    # 1 for each node
    while temp:
        len += 1
        temp = temp.next
    # Return the number of nodes in the linked list
    return len

# Function to get the middle value of the linked list
def getMiddle(head):
    # find length
    len = getLen(head)
    temp = head

    # traverse till we reached half of length
    midIdx = len // 2
    while midIdx:
        temp = temp.next
        midIdx -= 1
    # temp will be storing middle element
    return temp.data


# Driver Code
head = [None]
for i in range(5, 0, -1):
    pushNode(head, i)
print("Middle Value Of Linked List is:", getMiddle(head[0]))

Output
Middle Value Of Linked List is: 3

Time Complexity: O(2 * N) = O(N) where N is the number of nodes in the linked list.
Auxiliary Space: O(1)

Find Middle of the Linked List by Counting Nodes (One-pass):

Initialize an extra pointer, say mid with the head of the linked list and a counter to count the number of nodes in the linked list. Now, we traverse the linked list and increment the counter for each node and every time the value of counter becomes even, we move the mid pointer forward. As soon as we reach the end of the linked list, we return the mid pointer.

Step-by-step algorithm:

  • Initialize a pointer, say mid = head and a variable counter = 1 to count the number of nodes in the linked list.
  • Iterate till we reach the end of the linked list and increment counter = counter + 1 for each node.
  • In each iteration, check if the the value counter is even, then move the mid pointer to the next node.
  • After traversing the entire linked list, return the value at mid as the middle element of the linked list.

Below is the implementation of the algorithm:

C++ 
#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
      Node(int x) {
        data = x;
          next = NULL;
    }
};

// Function to add a new node
void pushNode(Node** head_ref, int data_val)
{
    // Allocate node
    Node* new_node = new Node(data_val);

    // Link the old list of the new node
    new_node->next = *head_ref;

    // move the head to point to the new node
    *head_ref = new_node;
}

// function to find the middle of the linked list
int getMiddle(Node* head)
{
    Node* mid = head;
    int counter = 1;
    // Traverse over the entire linked list
    while (head) {
          // If counter is even, move the mid pointer to the
        // next node
        if (counter % 2 == 0) {
            mid = mid->next;
        }
        head = head->next;
        // Increment the counter for each node
        counter += 1;
    }
    return mid->data;
}

// Driver Code
int main()
{
    Node* head = NULL;
    for (int i = 5; i > 0; i--) {
        pushNode(&head, i);
    }
    cout << "Middle Value Of Linked List is: "
         << getMiddle(head) << endl;
    return 0;
}
Java 
class Node {
    int data;
    Node next;
      Node(int x) {
        data = x;
          next = null;
    }
}

public class GFG {
    // Function to add a new node
    static void pushNode(Node[] head_ref, int data_val)
    {
        // Allocate node
        Node new_node = new Node(data_val);
        // Link the old list of the new node
        new_node.next = head_ref[0];
        // Move the head to point to the new node
        head_ref[0] = new_node;
    }

    // Function to find the middle of the linked list
    static int getMiddle(Node head)
    {
        Node mid = head;
        int counter = 1;
        // Traverse over the entire linked list
        while (head != null) {
            // If counter is even, move the mid pointer to
            // the next node
            if (counter % 2 == 0) {
                mid = mid.next;
            }
            head = head.next;
            // Increment the counter for each node
            counter++;
        }
        return mid.data;
    }

    // Driver Code
    public static void main(String[] args)
    {
        Node[] head = new Node[1];
        for (int i = 5; i > 0; i--) {
            pushNode(head, i);
        }
        System.out.println(
            "Middle Value Of Linked List is: "
            + getMiddle(head[0]));
    }
}
C# 
using System;

public class Node {
    public int data;
    public Node next;
      public Node(int x) {
        data = x;
          next = null;
    }
}

public class MainClass {
    // Function to add a new node
    static void pushNode(ref Node head_ref, int data_val)
    {
        // Allocate node
        Node new_node = new Node(data_val);
        // Link the old list of the new node
        new_node.next = head_ref;
        // Move the head to point to the new node
        head_ref = new_node;
    }

    // Function to find the middle of the linked list
    static int getMiddle(Node head)
    {
        Node mid = head;
        int counter = 1;
        // Traverse over the entire linked list
        while (head != null) {
            // If counter is even, move the mid pointer to
            // the next node
            if (counter % 2 == 0) {
                mid = mid.next;
            }
            head = head.next;
            // Increment the counter for each node
            counter++;
        }
        return mid.data;
    }

    // Driver Code
    public static void Main()
    {
        Node head = null;
        for (int i = 5; i > 0; i--) {
            pushNode(ref head, i);
        }
        Console.WriteLine("Middle Value Of Linked List is: "
                          + getMiddle(head));
    }
}
JavaScript 
class Node {
    constructor(x) {
        this.data = x;
        this.next = null;
    }
}

// Function to add a new node
function pushNode(head_ref, data_val) {
    // Allocate node
    let new_node = new Node(data_val);
    // Link the old list of the new node
    new_node.next = head_ref[0];
    // Move the head to point to the new node
    head_ref[0] = new_node;
}

// Function to find the middle of the linked list
function getMiddle(head) {
    let mid = head;
    let counter = 1;
    // Traverse over the entire linked list
    while (head !== null) {
        // If counter is even, move the mid pointer to the next node
        if (counter % 2 === 0) {
            mid = mid.next;
        }
        head = head.next;
        // Increment the counter for each node
        counter++;
    }
    return mid.data;
}

// Driver Code
let head = [null];
for (let i = 5; i > 0; i--) {
    pushNode(head, i);
}
console.log("Middle Value Of Linked List is: " + getMiddle(head[0]));
Python3 
class Node:
    def __init__(self, x):
        self.data = x
        self.next = None

# Function to add a new node


def pushNode(head_ref, data_val):
    # Allocate node
    new_node = Node(data_val)
    # Link the old list of the new node
    new_node.next = head_ref[0]
    # Move the head to point to the new node
    head_ref[0] = new_node

# Function to find the middle of the linked list


def getMiddle(head):
    mid = head
    counter = 1
    # Traverse over the entire linked list
    while head:
        # If counter is even, move the mid pointer to the next node
        if counter % 2 == 0:
            mid = mid.next
        head = head.next
        # Increment the counter for each node
        counter += 1
    return mid.data


# Driver Code
head = [None]
for i in range(5, 0, -1):
    pushNode(head, i)
print("Middle Value Of Linked List is:", getMiddle(head[0]))

Output
Middle Value Of Linked List is: 3

Time Complexity: O(N), where N is the number of nodes in the linked list.
Auxiliary Space: O(1)

Find Middle of the Linked List using Floyd’s Cycle Finding Algorithm:

We can use the Floyd’s Cycle Finding Algorithm, also known as Hare and Tortoise Algorithm to find the middle of the linked list. Traverse linked list using a slow pointer and a fast pointer. Move the slow pointer to the next node(one node forward) and the fast pointer to the next of the next node(two nodes forward). When the fast pointer reaches the last node or NULL, then the slow pointer will reach the middle of the linked list.

In case of odd number of nodes in the linked list, slow_ptr will reach the middle node when fast_ptr will reach the last node and in case of even number of nodes in the linked list, slow_ptr will reach the middle node when fast_ptr will become NULL.

Step-by-step algorithm:

  • Initialize a slow pointer slow_ptr = head and a fast pointer fast_ptr = head.
  • Iterate till fast_ptr reaches the last node(fast_ptr->next != NULL) or becomes NULL(fast_ptr != NULL).
  • Move fast_ptr by two nodes, fast_ptr = fast_ptr->next->next.
  • Move slow_ptr by one node, slow_ptr = slow_ptr->next.
  • As soon as the fast_ptr reaches the last node or becomes NULL, return the value at slow_ptr.

Below image shows how getMiddle() function works in the code:

Below is the implementation of the above algorithm:

C++ 
#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
      Node(int x) {
        data = x;
          next = NULL;
    }
};

// Function to add a new node
void pushNode(class Node** head_ref, int data_val)
{

    // Allocate node
    class Node* new_node = new Node(data_val);

    // Link the old list of the new node
    new_node->next = *head_ref;

    // move the head to point to the new node
    *head_ref = new_node;
}

// Function to get the middle of the linked list
int getMiddle(class Node* head)
{
    // Initialize the slow and fast pointer to the head of
    // the linked list
    struct Node* slow_ptr = head;
    struct Node* fast_ptr = head;

    while (fast_ptr != NULL && fast_ptr->next != NULL) {
        // Move the fast pointer by two nodes
        fast_ptr = fast_ptr->next->next;
        // Move the slow pointer by one node
        slow_ptr = slow_ptr->next;
    }
    return slow_ptr->data;
}

// Driver Code
int main()
{
    class Node* head = NULL;
    for (int i = 5; i > 0; i--) {
        pushNode(&head, i);
    }
    cout << "Middle Value Of Linked List is: "
         << getMiddle(head) << endl;
    return 0;
}
C 
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

// Function to add a new node
void pushNode(struct Node** head_ref, int data_val)
{
    // Allocate node
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));
    // Check if memory allocation was successful
    if (new_node == NULL) {
        printf("Memory allocation failed.\n");
        exit(1);
    }
    // Put in the data
    new_node->data = data_val;

    // Link the old list of the new node
    new_node->next = *head_ref;

    // move the head to point to the new node
    *head_ref = new_node;
}

// Function to get the middle of the linked list
int getMiddle(struct Node* head)
{
    // Initialize the slow and fast pointer to the head of
    // the linked list
    struct Node* slow_ptr = head;
    struct Node* fast_ptr = head;

    while (fast_ptr != NULL && fast_ptr->next != NULL) {
        // Move the fast pointer by two nodes
        fast_ptr = fast_ptr->next->next;
        // Move the slow pointer by one node
        slow_ptr = slow_ptr->next;
    }
    return slow_ptr->data;
}

// Driver Code
int main()
{
    struct Node* head = NULL;
    for (int i = 5; i > 0; i--) {
        pushNode(&head, i);
    }
    printf("Middle Value Of Linked List is: %d\n",
           getMiddle(head));
    return 0;
}
Java 
class Node {
    int data;
    Node next;
      Node(int x) {
        data = x;
          next = null;
    }
}

public class Main {
    // Function to add a new node
    static void pushNode(Node[] head_ref, int data_val)
    {
        // Allocate node
        Node new_node = new Node(data_val);
        // Link the old list of the new node
        new_node.next = head_ref[0];
        // Move the head to point to the new node
        head_ref[0] = new_node;
    }
    
      // Function to get the middle of the linked list
    static int getMiddle(Node head)
    {
        // Initialize the slow and fast pointer to the head
        // of the linked list
        Node slow_ptr = head;
        Node fast_ptr = head;

        while (fast_ptr != null && fast_ptr.next != null) {
            // Move the fast pointer by two nodes
            fast_ptr = fast_ptr.next.next;
            // Move the slow pointer by one node
            slow_ptr = slow_ptr.next;
        }
        return slow_ptr.data;
    }

    public static void main(String[] args)
    {
        Node[] head = new Node[1];
        for (int i = 5; i > 0; i--) {
            pushNode(head, i);
        }
        System.out.println(
            "Middle Value Of Linked List is: "
            + getMiddle(head[0]));
    }
}
C# 
using System;

public class Node {
    public int data;
    public Node next;
      public Node(int x) {
        data = x;
          next = null;
    }
}

public class MainClass {
    // Function to add a new node
    static void pushNode(ref Node head_ref, int data_val)
    {
        // Allocate node
        Node new_node = new Node(data_val);
        // Link the old list of the new node
        new_node.next = head_ref;
        // Move the head to point to the new node
        head_ref = new_node;
    }
    
      // Function to get the middle of the linked list
    static int getMiddle(Node head)
    {
        // Initialize the slow and fast pointer to the head
        // of the linked list
        Node slow_ptr = head;
        Node fast_ptr = head;

        while (fast_ptr != null && fast_ptr.next != null) {
            // Move the fast pointer by two nodes
            fast_ptr = fast_ptr.next.next;
            // Move the slow pointer by one node
            slow_ptr = slow_ptr.next;
        }
        return slow_ptr.data;
    }

    public static void Main()
    {
        Node head = null;
        for (int i = 5; i > 0; i--) {
            pushNode(ref head, i);
        }
        Console.WriteLine("Middle Value Of Linked List is: "
                          + getMiddle(head));
    }
}
Javascript 
class Node {
    constructor(x) {
        this.data = x;
        this.next = null;
    }
}

// Function to add a new node
function pushNode(head_ref, data_val) {
    // Allocate node
    let new_node = new Node(data_val);
    // Link the old list of the new node
    new_node.next = head_ref[0];
    // Move the head to point to the new node
    head_ref[0] = new_node;
}

// Function to get the middle of the linked list
function getMiddle(head) {
    // Initialize the slow and fast pointer to the head of
    // the linked list
    let slow_ptr = head;
    let fast_ptr = head;

    while (fast_ptr !== null && fast_ptr.next !== null) {
        // Move the fast pointer by two nodes
        fast_ptr = fast_ptr.next.next;
        // Move the slow pointer by one node
        slow_ptr = slow_ptr.next;
    }
    return slow_ptr.data;
}

// Driver Code
let head = [null];
for (let i = 5; i > 0; i--) {
    pushNode(head, i);
}
console.log("Middle Value Of Linked List is: " + getMiddle(head[0]));
Python3 
class Node:
    def __init__(self, x):
        self.data = x
        self.next = None

# Function to add a new node
def pushNode(head_ref, data_val):
    # Allocate node
    new_node = Node(data_val)
    # Link the old list of the new node
    new_node.next = head_ref[0]
    # Move the head to point to the new node
    head_ref[0] = new_node

# Function to get the middle of the linked list
def getMiddle(head):
    # Initialize the slow and fast pointer to the head of
    # the linked list
    slow_ptr = head
    fast_ptr = head

    while fast_ptr is not None and fast_ptr.next is not None:
        # Move the fast pointer by two nodes
        fast_ptr = fast_ptr.next.next
        # Move the slow pointer by one node
        slow_ptr = slow_ptr.next

    return slow_ptr.data


# Driver Code
head = [None]
for i in range(5, 0, -1):
    pushNode(head, i)
print("Middle Value Of Linked List is:", getMiddle(head[0]))

Output
Middle Value Of Linked List is: 3

Time Complexity: O(N), where N is the number of nodes in the linked list.
Auxiliary Space: O(1)
 

  
 



Like Article
Suggest improvement
Previous
Program for Nth node from the end of a Linked List
Next
Write a function that counts the number of times a given int occurs in a Linked List
Share your thoughts in the comments

Similar Reads

Find middle of singly linked list Recursively
Find kth node from Middle towards Head of a Linked List
XOR Linked List - Find the middle node
Given a linked list of line segments, remove middle points
Iterative approach for removing middle points in a linked list of line segments
Insert N elements in a Linked List one after other at middle position
Traverse Linked List from middle to left-right order using recursion
Java Program to Insert a New Node at the Middle of the Circular Linked List
C++ Program For Removing Middle Points From a Linked List Of Line Segments
C Program For Removing Middle Points From a Linked List Of Line Segments
https://media.geeksforgeeks.org/auth/avatar.png
GeeksforGeeks
Article Tags :
Practice Tags :
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox