CODEWITHSUNDEEP
javaalgorithmdata-structures
venky
venky

Reputation: 3

How to find the 2nd element from mid element of linkedlist?

In interview asked me to find out the value in the 2nd node from mid node of linked list? They expected to do this in a O(n) time complexity.

I have tried to give the answer to get the mid element using O(n2). But this could not help much. Then tried to do in O(n) using slow and fast pointers.

Node slow, fast;

    while (slow.next != null and fast.next.next != null){

    }

Eg. Input linked list: 1 2 3 4 5 6 7 8 9 Output Node: 7

Because mid node is 5 and 2nd element from it is 7.

Solutions are much appreciated.

Upvotes: 0

Views: 118

Answers (4)

uneq95
uneq95

Reputation: 2228

The approach is to find the node in the middle of the linked list, using the slow-fast pointer method. Then just find the next node of next node of middle node.

This way you can get the required node in O(1) space and O(N) time complexity.

@sourabh1024 has written the code. Take a look.

Upvotes: 0

sourabh1024
sourabh1024

Reputation: 657

Node getSecondAfterMind(Node head) {
  Node slow = head, fast = head;
  while(fast.next.next != NULL) {
    slow = slow.next;
    fast = fast.next.next;
  }
  if slow.next!= NULL && slow.next.next != NULL {
      return slow.next.next;
  }

   return NULL;
}

Upvotes: 2

Mark Melgo
Mark Melgo

Reputation: 1478

Another solution could be to iterate the linked list directly if you have a variable that holds the size of the linked list.

  1. Get the middle index by dividing the size by 2
  2. Increment this index by 2 (Let's call it midPlusTwo)
  3. Iterate the linked list and make a counter.
  4. Stop when the counter is equal to midPlusTwo

Upvotes: 0

Pavel Smirnov
Pavel Smirnov

Reputation: 4799

One of the solutions could be:

  1. Iterate over the linked list from the beginning to the end and put the reference of each element into List.
  2. When you hit the end of the linked list, find the index (i) of the middle element based on the size of the list.
  3. Increment this index by 2 (i + 2).
  4. Follow the reference from the List at index i + 2
  5. You got the element.

Upvotes: 1

Related Questions