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

I don't see how you could do it without traversing the entire list unless you know the length.

I'm guessing the answer wants one pointer to be traversing one element at a time, while the second pointer moves 2 elements at a time.
This way when the second pointer reaches the end, the first pointer will be at the middle.

Answer 2

In C, using pointers, for completeness. Note that this is based on the "Tortoise and Hare" algorithm used for checking if a linked list contains a cycle.

Our node is defined as the following:

typedef struct node {
    int          val;
    struct node *next;
} node_t;

Then our algorithm is thus:

node_t *
list_middle (node_t *root)
{
    node_t *tort = root;
    node_t *hare = root;

    while (hare != NULL && hare->next != NULL) {
        tort = tort->next;
        hare = hare->next->next;
    }

    return (tort);
}

For a list with an even number of nodes this returns the node proceding the actual centre (e.g. in a list of 10 nodes, this will return node 6).

Answer 3

LinkedList.Node current = head;
  int length = 0;
  LinkedList.Node middle = head;

  while(current.next() != null){
      length++;
      if(length%2 ==0){
          middle = middle.next();
      }
      current = current.next();
  }

  if(length%2 == 1){
      middle = middle.next();
  }

  System.out.println("length of LinkedList: " + length);
  System.out.println("middle element of LinkedList : " + middle);

Answer 4

Using C# to find a middle element of the linked list

    static void Main(string[] args)
    {
        LinkedList<int> linked = new LinkedList<int>();
        linked.AddLast(1);
        linked.AddLast(3);
        linked.AddLast(5);
        linked.AddLast(6);
        linked.AddFirst(12);

        Console.WriteLine("Middle Element - "+ListMiddle<int>(linked));
        Console.ReadLine(); }   

public static T ListMiddle<T>(IEnumerable<T> input)
    {
        if (input == null)
            return default(T);

        var slow = input.GetEnumerator();
        var fast = input.GetEnumerator();

        while (slow.MoveNext())
        {
            if (fast.MoveNext())
            {
                if (!fast.MoveNext())
                    return slow.Current;
            }
            else
            {
                return slow.Current;
            }
        }
        return slow.Current;
    }

Answer 5

The below code will help you get the middle element. You need to use two pointers "fast" and "slow". At every step the fast pointer will increment by two and slower will increment by one. When the list will end the slow pointer will be at the middle.

Let us consider the Node looks like this

class Node
{
  int data;
  Node next;
}

And LinkedList has a getter method to provide the head of the linked list

public Node getHead()
{
  return this.head;
}

The below method will get the middle element of the list (Without knowing the size of the list)

public int getMiddleElement(LinkedList l)
{
    return getMiddleElement(l.getHead());
}

private int getMiddleElement(Node n)
{
    Node slow = n;
    Node fast = n;

    while(fast!=null && fast.next!=null)
    {
        fast = fast.next.next;
        slow = slow.next;
    }

    return slow.data;
}

Example:
If the list is 1-2-3-4-5 the middle element is 3
If the list is 1-2-3-4 the middle element is 3

Answer 6

Using a size variable you can maintain the size of the Linked list.

public class LinkedList {
private Node headnode;
private int size;


public void add(int i){
    Node node = new Node(i);
    node.nextNode = headnode;

    headnode = node;
    size++;
}

public void findMiddleNode(LinkedList linkedList, int middle) {
    Node headnode = linkedList.getHeadnode();
    int count = -1;
    while (headnode!=null){
        count++;

        if(count == middle){
            System.out.println(headnode.data);
        }else {
            headnode = headnode.nextNode;
        }

    }
}


private class Node {
    private Node nextNode;
    private int data;

    public Node(int data) {
        this.data = data;
        this.nextNode = null;
    }
}

public Node getHeadnode() {
    return headnode;
}

public int getSize() {
    return size;
}
}

Then from a client method find the middle of the size of the list:

public class MainLinkedList {
public static void main(String[] args) {
    LinkedList linkedList = new LinkedList();
    linkedList.add(5);
    linkedList.add(3);
    linkedList.add(9);
    linkedList.add(4);
    linkedList.add(7);
    linkedList.add(99);
    linkedList.add(34);
    linkedList.add(798);
    linkedList.add(45);
    linkedList.add(99);
    linkedList.add(46);
    linkedList.add(22);
    linkedList.add(22);


    System.out.println(linkedList.getSize());

    int middle = linkedList.getSize()/2;

    linkedList.findMiddleNode(linkedList, middle);

}
}

I dont know if this is better than the two node way, but here also you dont have to traverse through the entire loop.