Find the middle of a given linked list in Java

Given a singly linked list, find middle of the linked list. For example, if given linked list is 1->2->3->4->5 then output should be 3.

If there are even nodes, then there would be two middle nodes, we need to print second middle element. For example, if given linked list is 1->2->3->4->5->6 then output should be 4.

Input : list: 1->2->4->5
        x = 3
Output : 1->2->3->4->5

Input : list: 5->10->4->32->16
        x = 41
Output : 5->10->4->41->32->16

Method 1(Using length of the linked list):
Find the number of nodes or length of the linked using one traversal. Let it be len. Calculate c = (len/2), if len is even, else c = (len+1)/2, if len is odd. Traverse again the first c nodes and insert the new node after the cth node.
// Java implementation to insert node
// at the middle of the linked list
import java.util.*;
import java.lang.*;
import java.io.*;
class LinkedList
{
    static Node head; // head of list
    /* Node Class */
    static class Node {
        int data;
        Node next;
        
        // Constructor to create a new node
        Node(int d) {
            data = d;
            next = null;
        }
    }
    // function to insert node at the
    // middle of the linked list
    static void insertAtMid(int x)
    {
        // if list is empty
        if (head == null)
            head = new Node(x);
        else {
            // get a new node
            Node newNode = new Node(x);
            Node ptr = head;
            int len = 0;
            // calculate length of the linked list
            //, i.e, the number of nodes
            while (ptr != null) {
                len++;
                ptr = ptr.next;
            }
            // 'count' the number of nodes after which
            // the new node is to be inserted
            int count = ((len % 2) == 0) ? (len / 2) :
                                        (len + 1) / 2;
            ptr = head;
            // 'ptr' points to the node after which
            // the new node is to be inserted
            while (count-- > 1)
                ptr = ptr.next;
            // insert the 'newNode' and adjust
            // the required links
            newNode.next = ptr.next;
            ptr.next = newNode;
        }
    }
    // function to display the linked list
    static void display()
    {
        Node temp = head;
        while (temp != null)
        {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }
    // Driver program to test above
    public static void main (String[] args)
    {
        // Creating the list 1.2.4.5
        head = null;
        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(4);
        head.next.next.next = new Node(5);
        
        System.out.println("Linked list before "+
                           "insertion: ");
        display();
        int x = 3;
        insertAtMid(x);
        System.out.println("\nLinked list after"+
                           " insertion: ");
        display();
    }
}
// This article is contributed by Chhavi

Output:

Linked list before insertion: 1 2 4 5
Linked list after insertion: 1 2 3 4 5

Time Complexity: O(n)

Method 2(Using two pointers):
Based on the tortoise and hare algorithm which uses two pointers, one known as slow and the other known as fast. This algorithm helps in finding the middle node of the linked list. It is explained in the front and black split procedure of this post. Now, you can insert the new node after the middle node obtained from the above process. This approach requires only a single traversal of the list.

// Java implementation to insert node
// at the middle of the linked list
import java.util.*;
import java.lang.*;
import java.io.*;
class LinkedList
{
    static Node head; // head of list
    /* Node Class */
    static class Node {
        int data;
        Node next;
        
        // Constructor to create a new node
        Node(int d) {
            data = d;
            next = null;
        }
    }
    // function to insert node at the
    // middle of the linked list
    static void insertAtMid(int x)
    {
        // if list is empty
        if (head == null)
        head = new Node(x);
        else {
            // get a new node
            Node newNode = new Node(x);
            // assign values to the slow
            // and fast pointers
            Node slow = head;
            Node fast = head.next;
            while (fast != null && fast.next
                                  != null)
            {
                // move slow pointer to next node
                slow = slow.next;
                // move fast pointer two nodes
                // at a time
                fast = fast.next.next;
            }
            // insert the 'newNode' and adjust
            // the required links
            newNode.next = slow.next;
            slow.next = newNode;
        }
    }
    // function to display the linked list
    static void display()
    {
        Node temp = head;
        while (temp != null)
        {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }
    // Driver program to test above
    public static void main (String[] args)
    {
        // Creating the list 1.2.4.5
        head = null;
        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(4);
        head.next.next.next = new Node(5);
        
        System.out.println("Linked list before"+
                           " insertion: ");
        display();
        int x = 3;
        insertAtMid(x);
        System.out.println("\nLinked list after"+
                           " insertion: ");
        display();
    }
}
// This article is contributed by Chhavi

Output:

Linked list before insertion: 1 2 4 5
Linked list after insertion: 1 2 3 4 5

Time Complexity: O(n)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s