Odd Even Linked List

328. 奇偶链表

分析

特例处理：
- 如果链表为空，或只有一个节点，则无需操作，直接返回原链表
分离奇偶链表：
- 定义两个链表头指针：
  - odd_head：奇数节点的头指针，初始为 head
  - even_head：偶数节点的头指针，初始为 head->next
- 遍历链表：
  - 用 odd_tail 和 even_tail 分别维护奇数链表和偶数链表的尾节点
  - 根据节点的索引位置，交替更新奇数链表和偶数链表的尾节点
拼接奇偶链表：
- 将奇数链表的尾节点连接到偶数链表的头节点
- 将偶数链表的尾节点指向 nullptr
返回结果：
- 返回奇数链表的头节点 odd_head

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


class Solution
{
public:
    ListNode* oddEvenList(ListNode* head)
    {
        // 特例处理：链表为空或只有一个节点
        if (!head || !head->next)
            return head;

        // 初始化奇数链表和偶数链表的头尾指针
        ListNode *odd_head = head, *odd_tail = odd_head;
        ListNode *even_head = head->next, *even_tail = even_head;

        // 遍历链表，交替处理奇数节点和偶数节点
        for (ListNode* p = head->next->next; p;)
        {
            // 处理奇数节点
            odd_tail = odd_tail->next = p;
            p = p->next;

            // 处理偶数节点
            if (p)
            {
                even_tail = even_tail->next = p;
                p = p->next;
            }
        }

        // 拼接奇数链表和偶数链表
        odd_tail->next = even_head;
        even_tail->next = nullptr;

        return odd_head;
    }
};