LeetCode题练习与总结：奇偶链表--328

一、题目描述

给定单链表的头节点 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^4
• -10^6 <= Node.val <= 10^6

二、解题思路

1. 创建两个哑节点（dummy node），分别用于连接奇数节点和偶数节点。哑节点的下一个节点分别是奇数链表的头节点和偶数链表的头节点。
2. 使用两个指针 odd 和 even 分别指向奇数节点和偶数节点的当前末尾。
3. 遍历原始链表，根据节点的索引是奇数还是偶数，将节点分别添加到奇数链表和偶数链表的末尾。
4. 遍历结束后，将偶数链表的头节点连接到奇数链表的末尾。
5. 返回奇数链表的头节点（即哑节点的下一个节点）。

三、具体代码

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) return null;

        // 创建两个哑节点
        ListNode odd = new ListNode(0);
        ListNode even = new ListNode(0);
        // 初始化两个指针分别指向奇数链表和偶数链表的末尾
        ListNode oddTail = odd, evenTail = even;
        // 当前节点的索引
        int index = 1;

        while (head != null) {
            if (index % 2 == 1) {
                // 奇数索引，添加到奇数链表
                oddTail.next = head;
                oddTail = oddTail.next;
            } else {
                // 偶数索引，添加到偶数链表
                evenTail.next = head;
                evenTail = evenTail.next;
            }
            // 移动到下一个节点
            head = head.next;
            index++;
        }

        // 将偶数链表连接到奇数链表的末尾
        oddTail.next = even.next;
        // 断开偶数链表的末尾，防止形成环
        evenTail.next = null;

        // 返回重新排序的链表头节点
        return odd.next;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• 遍历链表：代码中有一个 while 循环，该循环会遍历链表中的每个节点一次。因此，这个循环的时间复杂度是 O(n)，其中 n 是链表中的节点数。
• 在循环内部，我们进行了一些常数时间的操作（如判断索引的奇偶性、更新指针等），这些操作的时间复杂度都是 O(1)。
• 因此，总的时间复杂度是 O(n)，因为我们只遍历了一次链表。

2. 空间复杂度

• 代码中使用了固定数量的额外空间，即创建了两个哑节点 odd 和 even，以及两个指针 oddTail 和 evenTail。无论输入链表的大小如何，这些额外空间的大小都是固定的。
• 除了这些额外的变量，我们没有使用任何其他与链表大小相关的数据结构（如数组、哈希表等）。
• 因此，空间复杂度是 O(1)，表示额外空间的使用量不随输入链表的大小而变化。

五、总结知识点

• 链表（Linked List）：

  • 链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据域和指向下一个节点的指针。
  • 链表的节点通过指针连接，不需要连续的内存空间。

• 哑节点（Dummy Node）：

  • 哑节点是一种技巧，通常用于简化边界条件处理，使得代码更加简洁。
  • 在本代码中，哑节点用于简化对链表头部的操作，无需单独处理头节点的情况。

• 指针（Pointer）：

  • 指针用于在内存中存储和访问地址。
  • 在链表操作中，指针用于遍历和修改节点之间的连接关系。

• 循环（Loop）：

  • while 循环用于遍历链表中的所有节点。
  • 循环内部进行条件判断和节点指针的更新。

• 条件判断（Conditional Statements）：

  • if-else 语句用于根据节点索引的奇偶性将节点分配到不同的链表。

• 算术运算（Arithmetic Operations）：

  • 取模运算 % 用于判断索引的奇偶性。

• 递增操作（Increment Operation）：

  • index++ 用于在每次循环时递增索引。

• 链表连接（Linking Lists）：

  • 通过更新节点的 next 指针，将奇数链表和偶数链表连接起来。

• 链表断开（Breaking Links in a List）：

  • 将偶数链表的末尾节点的 next 指针设置为 null，以防止形成环。

• 返回值（Return Value）：

  • 函数返回重新排序后的链表的头节点，即哑节点的下一个节点。

• 空指针检查（Null Pointer Check）：

  • 在函数开始时检查头节点是否为 null，以处理空链表的情况。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。