What is the main challenge in Odd Even Linked List?

The primary challenge is correctly manipulating pointers in a single pass to separate odd and even nodes without losing the original relative order.

Can I solve Odd Even Linked List with extra arrays?

Yes, but using extra arrays increases space complexity and is generally discouraged in interviews that focus on in-place pointer manipulation.

Does node value affect whether it is odd or even?

No, the odd and even grouping is based on node positions, not the values stored in the nodes.

What edge cases should I consider?

Empty lists, single-node lists, and lists with only even or only odd nodes are critical edge cases to handle correctly.

How do I merge the odd and even sublists safely?

Keep a reference to the head of the even sublist, and after processing all nodes, set the next pointer of the last odd node to this even head, ensuring the last even node points to null.

#328

Medium

auto_awesome链表指针操作

LeetCode 题解工作台

奇偶链表

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别分组，保持它们原有的相对顺序，然后把偶数索引节点分组连接到奇数索引节点分组之后，返回重新排序的链表。第一个节点的索引被认为是奇数，第二个节点的索引为偶数，以此类推。请注意，偶数组和奇数组内部的相对顺序应该与…

链表

题目描述

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别分组，保持它们原有的相对顺序，然后把偶数索引节点分组连接到奇数索引节点分组之后，返回重新排序的链表。

第一个节点的索引被认为是奇数， 第二个节点的索引为偶数，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

示例 1:

输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]

示例 2:

输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]

提示:

n == 链表中的节点数
0 <= n <= 10⁴
-10⁶ <= Node.val <= 10⁶

lightbulb

解题思路

方法一：一次遍历

我们可以用两个指针 $a$ 和 $b$ 分别表示奇数节点和偶数节点的尾节点。初始时，指针 $a$ 指向链表的头节点 $head$ ，指针 $b$ 指向链表的第二个节点 $head.next$ 。另外，我们用一个指针 $c$ 指向偶数节点的头节点 $head.next$ ，即指针 $b$ 的初始位置。

遍历链表，我们将指针 $a$ 指向 $b$ 的下一个节点，即 $a.next = b.next$ ，然后将指针 $a$ 向后移动一位，即 $a = a.next$ ；将指针 $b$ 指向 $a$ 的下一个节点，即 $b.next = a.next$ ，然后将指针 $b$ 向后移动一位，即 $b = b.next$ 。继续遍历，直到 $b$ 到达链表的末尾。

最后，我们将奇数节点的尾节点 $a$ 指向偶数节点的头节点 $c$ ，即 $a.next = c$ ，然后返回链表的头节点 $head$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 是链表的长度，需要遍历链表一次。空间复杂度 $O(1)$ 。只需要维护有限的指针。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None
        a = head
        b = c = head.next
        while b and b.next:
            a.next = b.next
            a = a.next
            b.next = a.next
            b = b.next
        a.next = c
        return head

speed

复杂度分析

指标	值
时间	complexity is O(n) because each node is visited exactly once. Space complexity is O(1) since no additional data structures are used beyond a few pointers, making this approach optimal for in-place reordering.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for in-place pointer manipulations without using extra arrays or lists.
question_mark
Check whether relative ordering of odd and even nodes is preserved.
question_mark
Watch for edge cases like empty lists, single-node lists, or lists with only even nodes.

warning

常见陷阱

外企场景

error
Failing to reconnect the even sublist to the odd sublist at the end.
error
Breaking the linked list by incorrectly updating next pointers, leading to cycles or null references.
error
Assuming node values determine odd/even instead of node positions, which is a common misinterpretation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Reordering nodes so that all nodes at prime indices appear before non-prime indices.
arrow_right_alt
Segregating linked list nodes based on alternating property, such as positive and negative values, instead of odd and even positions.
arrow_right_alt
Perform the reordering using a recursive approach instead of iterative pointer manipulation.

help

常见问题

外企场景

继续练习

#355 设计推特 #382 链表随机节点 #237 删除链表中的节点