用devC实现一下程序:有一个由整数元素构成的非空单链表A,设计一个算法,将其拆分成两个单链表A和B,使得A单链表中含有所有的偶数节点,B单链表中含有所有的奇数节点,且保持原来的相对次序。
时间: 2024-11-25 22:11:35 浏览: 3
要实现这个功能,你可以通过遍历链表并判断每个节点的值是否为偶数来进行操作。以下是使用C++和dev-C++编写的示例代码:
```cpp
#include <iostream>
using namespace std;
// 定义链表节点结构
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* oddEvenSplit(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head; // 如果链表为空或只有一个节点,直接返回
}
ListNode* oddHead = new ListNode(0); // 创建头结点,用于保存奇数部分
ListNode* evenHead = new ListNode(0); // 创建头结点,用于保存偶数部分
ListNode* current = head;
bool isOdd = true; // 初始状态为奇数序列
while (current != NULL) {
if (isOdd) {
oddHead->next = current;
oddHead = oddHead->next;
isOdd = false;
} else {
evenHead->next = current;
evenHead = evenHead->next;
isOdd = true;
}
current = current->next;
}
oddHead->next = nullptr;
evenHead->next = nullptr; // 结束部分加NULL
return isOdd ? oddHead : evenHead; // 返回奇数链表的头结点
}
// 打印链表帮助测试
void printList(ListNode* head) {
while (head != NULL) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
int main() {
// 初始化你的链表数据...
// 调用oddEvenSplit函数分割链表,并打印结果
ListNode* list = ...;
ListNode* result = oddEvenSplit(list);
printList(result);
return 0;
}
```
在这个代码中,我们创建了两个新的头结点`oddHead`和`evenHead`,然后遍历原链表,根据当前节点的值决定将它添加到哪一部分。最后返回相应的头结点,实现了链表的拆分。
阅读全文