设计算法将一个带头结点的单链表a分解为两个具有相同结构的链表b、c,其中b表的结点为a表中值小于零的结点,而c表的结点为a表中值大于零的结点(链表a中的元素为非零整数,要求b、c表利用a表的结点)。
时间: 2023-04-22 18:04:43 浏览: 123
C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现
算法步骤如下:
1. 创建两个新的链表b和c,分别表示值小于零和值大于零的结点。
2. 遍历链表a,将值小于零的结点插入到链表b的末尾,将值大于零的结点插入到链表c的末尾。
3. 遍历完成后,链表a被分解为两个具有相同结构的链表b和c。
4. 返回链表b和c。
代码实现如下:
ListNode* partitionList(ListNode* a) {
ListNode* b = new ListNode(); // 创建链表b
ListNode* c = new ListNode(); // 创建链表c
ListNode* pb = b; // 指向链表b的末尾结点
ListNode* pc = c; // 指向链表c的末尾结点
ListNode* p = a->next; // 指向链表a的第一个结点
while (p != NULL) {
if (p->val < ) { // 如果值小于零,插入到链表b的末尾
pb->next = p;
pb = pb->next;
} else { // 如果值大于零,插入到链表c的末尾
pc->next = p;
pc = pc->next;
}
p = p->next;
}
pb->next = NULL; // 链表b的末尾结点指向NULL
pc->next = NULL; // 链表c的末尾结点指向NULL
a->next = NULL; // 链表a的末尾结点指向NULL
pb->next = c->next; // 链表b的末尾结点指向链表c的第一个结点
ListNode* result = b->next; // 返回链表b
delete b; // 释放链表b的头结点
delete c; // 释放链表c的头结点
return result;
}
阅读全文