How to Find a middle element in a link list withou

Question

How to find a middle element in a link list without traversing the entire list . ? ...and at the maximum you can use only 2 pointers...how to do ? .... and also the length of list is not given.

Answer 1

import java.util.*;
public class MainLinkedList {
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add(10);
linkedList.add(32);
linkedList.add(90);
linkedList.add(43);
linkedList.add(70);
linkedList.add(20);
linkedList.add(45);

int middle = linkedList.size()/2;
System.out.println(linkedList.get(middle));

} }

Answer 2

Python code for middle element using two pointer method:

class Node:
    def __init__(self,data):
        self.data=data
        self.next=None

class LinkedList:
    def __init__(self):
        self.head=None

    def printList(self):
        temp=self.head
        while(temp):
            print(temp.data,end=" ")
            temp=temp.next

    def insertAtBeg(self,new_data):
        new_node=Node(new_data)
        if self.head is None:
            self.head=new_node
            return

        new_node.next=self.head
        self.head=new_node

    def findMiddle(self):
        fast_ptr=self.head
        slow_ptr=self.head

        if(self.head is not None):
            while(fast_ptr is not None and fast_ptr.next is not None):
                fast_ptr=fast_ptr.next.next
                slow_ptr=slow_ptr.next
            print('Middle Element is '+ str (slow_ptr.data))

if __name__=='__main__':
    mylist=LinkedList()
    mylist.insertAtBeg(10)
    mylist.insertAtBeg(20)
    mylist.insertAtBeg(30)
    mylist.findMiddle()

Output: Middle Element is 20

Answer 3

There are two possible answers one for odd and one for even, both having the same algorithm

For odd: One pointer moves one step and second pointer moves two element as a time and when the second elements reach the last element, the element at which the first pointer is, the mid element. Very easy for odd. Try: 1 2 3 4 5

For even: Same, One pointer moves one step and second pointer moves two element as a time and when the second elements cannot jump to next element, the element at which the first pointer is, the mid element. Try: 1 2 3 4

Answer 4

For doubly linked list with given pointers to the head and tail node
we can use both head and tail traversal

p = head;
q = tail;
while(p != q && p->next != q)
{
    p = p->next;
    q = q->prev;
}
return p;

Introducing pointer to the middle node may be an option but functions like
insertNode and deleteNode have to modify this pointer

Answer 5

It's stupid to use two pointers "fast" and "slow".Beacause the operator next is used 1.5n times.There is no optimization.

Using a pointer to save the middle element can help you.

list* find_mid_1(list* ptr)
{
    list *p_s1 = ptr, *p_s2 = ptr;
    while (p_s2=p_s2->get_next())
    {
        p_s2 = p_s2->get_next();
        if (!p_s2)
            break;
        p_s1 = p_s1->get_next(); 
    }
    return p_s1;
}

Answer 6

I am adding my solution which will work for both odd and even number of elements scenarios like

1-2-3-4-5 middle element 3

1-2-3-4 middle element 2,3

It is inspired by same fast pointer and slow pointer principle as mentioned in some of the other answers in the post.

public class linkedlist{

Node head;

static class Node{
    int data;
    Node next;
    Node(int d)  { data = d;  next=null; } 
}
public static void main(String args[]){
    linkedlist ll = new linkedlist();       
    Node one = new Node(1);
    Node second = new Node(2);
    Node third = new Node(3);
    Node fourth = new Node(4);
    Node five = new Node(5);
    Node sixth = new Node(6);
    Node seventh = new Node(7);
    Node eight = new Node(8);
    ll.head = one;
    one.next = second;
    second.next = third;
    third.next = fourth;
    fourth.next = five;
    five.next = sixth;
    sixth.next = seventh;
    seventh.next = eight;
    ll.printList();
    ll.middleElement();
}
public void printList(){
    Node n = head;
    while( n != null){
        System.out.print(n.data+ "  ---> ");
        n = n.next;
    }
}

public void middleElement(){
    Node headPointer = head;
    Node headFasterPointer = head;
    int counter = 0;

    if(head != null){
    while(headFasterPointer.next != null ){

        if(headFasterPointer.next.next != null){
        headFasterPointer = headFasterPointer.next.next;
        headPointer = headPointer.next;
        } 
        else
         {
        headFasterPointer = headFasterPointer.next;
        } 
        counter++;
    }

    System.out.println();
    System.out.println("The value of counter is "+ counter);
    if(counter %2 == 0){
     System.out.println("The middle element is " + headPointer.data +","+ headPointer.next.data);
    } else 
    {
     System.out.println("The middle element is " + headPointer.data );
    }



    }

} }