algorithm to find middle element of linked list @ O(n/2) order

Since every node in a linked list has the reference to its next node, we can achieve this solution by taking two pointers.

For every increment in one pointer, increment the second pointer twice, in this way by the time second pointer reaches the end of the linked list, first pointer should reach the middle element of the linked list.

	public void traverse(Node node) {
		tmp = node;
		while (tmp != null && tmp.next != null) {
			node = node.next;
			tmp = tmp.next.next;
		}
		System.out.println("Middle element of the list is: " + node.value);
	}

Note: With this logic, in any linked list we can find 1/2th element (with above logic) OR 1/3rd element (by replacing the code ‘tmp = tmp.next.next;’ to tmp = tmp.next.next.next;) OR 1/4th element (by replacing the code ‘tmp = tmp.next.next;’ to tmp = tmp.next.next.next.next;), so on

Advertisements

One Response to algorithm to find middle element of linked list @ O(n/2) order

  1. kinshuk4 says:

    One very similar approach to it will be to use counter approach (though v.same to your approach) as mentioned here:
    // Function to get to the middle of the LL
    mynode *getTheMiddle(mynode *head)
    {
    mynode *middle = (mynode *)NULL;
    int i;
    for(i=1; head!=(mynode *)NULL; head=head->next,i++)
    {
    if(i==1)
    middle=head;
    else if ((i%2)==1)
    middle=middle->next;
    }
    return middle;
    }

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

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey