LeetCode奇偶链表问题：代码报错原因及修复请求

Hey there! Let's break down why that line odd_head.next = even_head is causing issues, and how to get your code working correctly.

What's Wrong with the Current Approach? #

Your code has a few key problems that lead to the bug:

1. You're breaking the even node chain while processing odds
   When you overwrite odd_head.next to jump to the next odd node, you're destroying the links that connect the even nodes together. By the time you try to process the even list, those nodes are no longer in a valid, connected chain—their pointers have been messed up by the odd node modifications.

2. You're returning the wrong node
   After the first loop finishes, odd_head is the last node in the odd list, not the head of the full rearranged list. Returning this will only give you the tail end of your desired result, not the complete linked list.

3. No cycle prevention for the even list
   Even if you fixed the first two issues, the last node in the even list might still point to an odd node, creating an infinite cycle in your final output.

How to Fix It #

The right approach is to traverse both odd and even nodes at the same time, building two separate, intact lists until the end. Then you can safely link the odd list's tail to the even list's head. Here's the step-by-step fix:

• Keep track of the original odd head (this will be your final return value) and the even head.
• Use two pointers (odd and even) to iterate through their respective nodes without breaking their chains prematurely.
• For each step:
  • Link the current odd node to the next odd node (which is even.next)
  • Move the odd pointer forward
  • Link the current even node to the next even node (now odd.next)
  • Move the even pointer forward
• Once traversal ends, connect the end of the odd list to the start of the even list.
• Ensure the last even node's next is set to None to avoid cycles.

Corrected Code #

def oddEvenList(self, head):
    if not head or not head.next:
        return head
    
    odd = head
    even_head = head.next
    even = even_head
    
    while even and even.next:
        # Link to the next odd node
        odd.next = even.next
        odd = odd.next
        # Link to the next even node
        even.next = odd.next
        even = even.next
    
    # Connect the end of odd list to the start of even list
    odd.next = even_head
    return head

Let's Walk Through the Example #

Take the input 2->1->3->5->6->4->7->NULL:

1. Initial state: odd = 2, even = 1, even_head = 1
2. First iteration:
   • odd.next = 1.next = 3 (so 2->3), odd moves to 3
   • even.next = 3.next =5 (so 1->5), even moves to5
3. Second iteration:
   • odd.next =5.next=6 (so 3->6), odd moves to6
   • even.next=6.next=4 (so 5->4), even moves to4
4. Third iteration:
   • odd.next=4.next=7 (so 6->7), odd moves to7
   • even.next=7.next=NULL (so 4->NULL), even moves to NULL
5. Loop ends, link 7.next = even_head (1)
6. Final list: 2->3->6->7->1->5->4->NULL which matches the expected output.

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