C++ 链表拆分

在C++编程中，链表是一种非常重要的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表拆分是指将一个链表按照特定规则（如奇数节点和偶数节点）拆分成两个独立的链表。在本问题中，我们需要实现一个C++函数，该函数接受一个链表头节点，然后将其拆分为两个链表，一个是奇数索引的节点，另一个是偶数索引的节点。 我们需要定义链表节点的结构体，通常称为`ListNode`： ```cpp struct ListNode { int val; // 节点值 ListNode *next; // 指向下一个节点的指针 ListNode(int x) : val(x), next(NULL) {} // 构造函数 }; ``` 接下来，我们将实现拆分链表的函数。这里我们采用迭代的方式，用两个指针分别跟踪奇数和偶数节点链表的当前节点，同时保持对原链表的遍历。代码如下： ```cpp ListNode* splitList(ListNode* head) { if (head == NULL || head->next == NULL) { // 如果链表为空或只有一个元素，无需拆分 return head; } ListNode* odd = head; // 奇数链表的头节点 ListNode* even = head->next; // 偶数链表的头节点 ListNode* temp_even = even; // 用于更新偶数链表的指针 odd->next = NULL; // 奇数链表的初始状态 while (even != NULL) { ListNode* next_even = even->next; even->next = temp_even; temp_even = even; odd->next = next_odd; odd = next_odd; even = next_even; } return odd; } ``` 在这个函数中，我们首先检查链表是否为空或只有一个元素，如果是，则直接返回原链表，因为不需要拆分。接着，我们初始化两个指针`odd`和`even`，分别表示新奇数链表和偶数链表的当前节点。`temp_even`用于存储偶数链表的下一个节点，以便于更新偶数链表。 在`while`循环中，我们不断遍历原链表，每次都将当前偶数节点连接到偶数链表的末尾，并将当前奇数节点连接到奇数链表的末尾。这样，当我们遍历完原链表后，两个新的链表已经形成，且原始链表的结构未被破坏。 我们返回奇数链表的头节点，因为偶数链表的头节点已经在初始化时设置好了。 这个实现的优点是它不占用额外的空间，且时间复杂度为O(n)，其中n是链表的长度。通过这种方法，我们可以有效地将一个链表拆分成两个满足特定条件的新链表。 总结来说，链表拆分是链表操作的一种常见任务，可以锻炼我们对链表的理解和操作能力。在C++中，通过迭代方式实现，可以高效地完成这一任务。理解并掌握这种技巧对于进行更复杂的链表操作，如合并、排序等，是非常有帮助的。