Middle of a Linked List

You are given the head node of a singly linked list. Your task is to return a pointer pointing to the middle of the linked list.

If there is an odd number of elements, return the middle element. If there are an even number of elements, return the one that is farther from the head node.

Example:

Input:
1->2->3->4->null
Output:
3
Explanation:

The input linked list has 4 elements, with 2 and 3 as potential middles. We return 3 because it is farther from the head node 1.

Input:

The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘2*T’ lines represent the ‘T’ test cases.
The first and only line of each test case contains integers denoting the nodes of the linked list. Each line is guaranteed to have -1 at the end to signify the end of the linked list.

Output:

For each test case, return a pointer pointing to the node which is at the middle of the linked list. If no midpoint exists, return a null pointer.

Constraints:

  • 1 <= T <= 50
  • 0 <= N <= 4*10^4
  • -10^9 <= data <= 10^9
  • data ≠ -1

Note:

  • You do not need to print anything, it has already been taken care of. Just implement the given function.
  • For a linked list of size 1, the head node is the midpoint.
  • If no midpoint exists, return a null pointer.
AnswerBot
1d

Return the middle element of a singly linked list, or the one farther from the head node if there are even elements.

  • Traverse the linked list with two pointers, one moving twice as fast as the other

  • Whe...read more

Help your peers!
Add answer anonymously...
Paytm Software Engineer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter