如何利用头节点(head)与尾节点(tail)查找双向链表中间元素？偶数节点时如何停止？

Great question! Your two-pointer approach (traversing from both ends) is a smart way to tackle this problem, but let's fix the loop condition to handle both odd and even-length lists correctly—including correcting a subtle issue with how your current code behaves for odd-length lists.

The Issue with Your Current Loop #

Your current condition while(head.next != end.previous) doesn't stop at the middle for odd-length lists, and it overshoots for even-length ones. For example, in a 5-node list (A↔B↔C↔D↔E), your loop would keep running until head reaches E and end reaches A, which is way past the actual middle node C.

The Correct Loop Condition #

We need to stop the loop when either:

• The two pointers meet (head == end): This is the odd-length case—this node is the single middle element.
• The pointers become adjacent (head.next == end): This is the even-length case—these two nodes are the two middle elements.

Here's the adjusted code:

// Initialize with your head and tail pointers
while (head != end && head.next != end) {
    head = head.next;
    end = end.previous;
}

How This Works (Step-by-Step) #

Let's test this with both scenarios:

Odd-Length List (5 nodes: A↔B↔C↔D↔E)

1. Start with head=A, end=E. Since head != end and head.next (B) != end (E), the loop runs. Head becomes B, end becomes D.
2. Now head != end and head.next (C) != end (D), loop runs again. Head becomes C, end becomes C.
3. Now head == end → loop stops. The middle element is head (or end, since they're the same node).

Even-Length List (4 nodes: A↔B↔C↔D)

1. Start with head=A, end=D. Since head != end and head.next (B) != end (D), loop runs. Head becomes B, end becomes C.
2. Now head.next (C) == end (C) → loop stops. The two middle elements are head (B) and end (C).

Handling the Result #

After the loop, you can check which condition was met to return the right middle element(s):

• If head == end: Return this single node as the middle.
• If head.next == end: Return both nodes (or pick one, depending on your use case—like the first middle or the second).

This approach runs in O(n/2) time, which is optimal since you only traverse half the list at most.

内容的提问来源于stack exchange，提问作者Karan Khanna