请利用单链表的基本运算实现以下功能:有一个单链表LA,数据域全部存放整数,设计算法将其拆分成两个单链表LA和LB,使得LA单链表中含有所有元素值为偶数的结点,LB单链表中含有的所有元素为奇数的结点,且保持原来的相对次序,输出LA和LB两个单链表中的元素值。完整代码
时间: 2024-03-03 10:47:44 浏览: 80
以下是利用单链表实现题目要求的完整代码:
```c++
#include <iostream>
using namespace std;
//定义单链表结点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
//将原链表拆分成两个链表,并返回新链表的头结点
ListNode* splitList(ListNode* head, ListNode*& evenHead, ListNode*& oddHead) {
//定义两个指针分别指向新链表的头结点
evenHead = new ListNode(0);
oddHead = new ListNode(0);
//定义两个指针分别指向原链表和新链表
ListNode* p = head;
ListNode* even = evenHead;
ListNode* odd = oddHead;
while (p != NULL) {
if (p->val % 2 == 0) { //如果是偶数结点
even->next = p;
even = even->next;
} else { //如果是奇数结点
odd->next = p;
odd = odd->next;
}
p = p->next;
}
//将新链表的尾结点指向NULL
even->next = NULL;
odd->next = NULL;
//返回新链表的头结点
return evenHead;
}
//输出链表中的元素值
void printList(ListNode* head) {
ListNode* p = head;
while (p != NULL) {
cout << p->val << " ";
p = p->next;
}
cout << endl;
}
int main() {
//创建链表LA
ListNode* LA = new ListNode(2);
LA->next = new ListNode(5);
LA->next->next = new ListNode(4);
LA->next->next->next = new ListNode(7);
LA->next->next->next->next = new ListNode(6);
LA->next->next->next->next->next = new ListNode(3);
LA->next->next->next->next->next->next = new ListNode(1);
//将链表LA拆分成两个链表
ListNode* evenHead = NULL;
ListNode* oddHead = NULL;
splitList(LA, evenHead, oddHead);
//输出两个链表中的元素值
cout << "even list: ";
printList(evenHead->next);
cout << "odd list: ";
printList(oddHead->next);
return 0;
}
```
输出结果为:
```
even list: 2 4 6
odd list: 5 7 3 1
```
阅读全文