链表的奇偶节点重新排列及空指针问题分析【链表、空指针】

在处理链表问题时，重组链表节点是一种常见需求。本文将详细探讨如何在链表中将奇数索引节点放在偶数索引节点之前，并深入分析实现过程中的空指针问题及其解决方案。

1. 问题描述

给定一个单链表，要求将链表中的节点按照奇数索引节点在前、偶数索引节点在后的顺序重新排列。节点索引从1开始，第一个节点为奇数位置，第二个节点为偶数位置，依此类推。

示例 1：
在这里插入图片描述

输入: [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]

问题来源：328. 奇偶链表 - 力扣（LeetCode）

2. 解决方案

我们可以通过两个指针（odd 和 even）分别追踪奇数索引节点和偶数索引节点，并通过交替操作这些指针来重新排列链表。

实现步骤

初始化指针：
- odd 指向链表的第一个节点，即奇数索引节点的头节点。
- even 指向链表的第二个节点，即偶数索引节点的头节点。
- evenHead 保存偶数节点链表的头，以便最后将奇数链表与偶数链表连接。
循环遍历链表：
- 在 even 和 even->next 都存在的前提下，依次重新链接奇数和偶数节点：
  - 先将 odd 指针指向的节点连接到下一个奇数节点上。
  - 再将 even 指针指向的节点连接到下一个偶数节点上。
连接两个链表：
- 最后，将奇数链表的最后一个节点的 next 指针指向偶数链表的头节点 evenHead，完成链表的重组。

3. 代码实现

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* oddEvenList(ListNode* head) {if (!head) return nullptr;  // 空链表直接返回ListNode* odd = head;  // 奇数节点的指针ListNode* even = head->next;  // 偶数节点的指针ListNode* evenHead = even;  // 保存偶数节点链表的头部// 交替更新奇数和偶数节点链表while (even && even->next) {odd->next = even->next;  // 将奇数节点指向下一个奇数节点odd = odd->next;  // 将奇数指针移动到下一个奇数节点even->next = odd->next;  // 将偶数节点指向下一个偶数节点even = even->next;  // 将偶数指针移动到下一个偶数节点}// 连接奇数和偶数节点链表odd->next = evenHead;return head;}
};

4. 空指针问题分析

在实现过程中，代码中可能出现一个常见的错误：未正确处理链表节点更新的顺序，从而导致访问空指针。以下详细分析为什么需要优先移动 odd 指针，以及为什么先移动 even 指针会导致空指针异常。

错误示例

even->next = odd->next;
even = even->next;
odd->next = even->next;  // 这里可能会出现空指针访问
odd = odd->next;

问题分析：

偶数指针先移动的危险：
- 假设我们首先更新 even 指针。当 even 指向链表的末尾（特别是在链表长度为偶数的情况下），even->next 可能为 nullptr。此时，odd->next 也变为 nullptr。如果在这种情况下继续访问 odd->next->next，就会导致访问空指针，触发运行时错误。
正确的指针更新顺序：
- 为了避免上述问题，我们应首先更新 odd 指针，然后再更新 even 指针。这是因为当我们移动 odd 指针时，odd->next 始终指向一个有效的奇数节点，保证了链表的结构不被破坏。随后再更新 even 指针，确保其安全性和有效性。

5. 解决方法

为了避免空指针问题，我们需要遵循以下几点原则：

先更新 odd 指针，再更新 even 指针：这样可以确保在整个操作过程中，odd 和 even 指针总是指向有效的节点，避免空指针访问。
链表末尾处理：在循环过程中，条件判断 while (even && even->next) 确保了 even 指针不会在不合法的位置进行访问，从而避免了潜在的空指针错误。