目录
一、有相对顺序的链表分割
二、无相对顺序的链表分割
一、有相对顺序的链表分割
题述:现有一链表的头指针ListNode* phead,给一定值x,编写一段代码将所有<x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排序后的链表的头指针。
示例如下:
思路:难就难在不能改变相对顺序。那我们的思路是创建两个链表,一个链表尾插<x的值,一个链表尾插>x的值,然后再把两个链表顺序链接即可。并且我们还会给两个链表定义尾指针,lessTail和greaterTail,并且会开辟一个头结点,这两个操作都是为了方便尾插。没有头结点还要多加一个判断。
但是如果开辟头结点,还要多两个操作:
1、我们题中默认都是没有头结点的,如果要返回头指针,他一定是要返回头结点的下一节点的地址,并且在两个链表链接过程中,一定是链接后面的头结点后的那一个节点。
2、要释放节点的内存,要返还给操作系统。
小知识:一般上oj上是不会限制空间复杂度的,如果出现报错,内存限制:您的程序使用了超出限制的内存。这种问题可能是由死循环等的问题造成的。
#include<stdio.h>
#include<stdlib.h>struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* partition(struct ListNode* phead, int x)
{struct ListNode* lessHead, * lessTail, * greaterHead, * greaterTail;lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));//开辟一个头结点,使头指针和尾指针都指向头结点,以便遍历链表greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur = phead;//用cur来遍历原链表while (cur)//结束条件一定是遍历完原链表{if (cur->val < x){lessTail->next = cur;lessTail = cur;}else{greaterTail->next = cur;greaterTail = cur;}cur = cur->next;//无论如何,链接完一个结点后都要往下走一次}lessTail->next = greaterHead->next;//将>=x的链表链接在<x的链表后面。//这里是=greaterHead->next的原因是greaterHead是头结点,是你自己开辟的,题里面不要这个!greaterTail->next = NULL;//使>=x的链表最后指向是NULL,防止构成环形链表struct ListNode* newnode = lessHead->next;//因为lessHead是头结点,我们不要!free(lessHead);//因为lessHead始终指向头结点,所以直接释放free(greaterHead);return newnode;
}
int main()
{struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));int k = 5;n1->val = 1;n2->val = 2;n3->val = 4;n4->val = 3;n5->val = 9;n1->next = n2;n2->next = n3;n3->next = n4;n4->next = n5;n5->next = NULL;struct ListNode* obj = partition(n1, k);while (obj){printf("%d", obj->val);obj = obj->next;}return 0;
}
运行代码如下:
如果不要求相对顺序呢?
二、无相对顺序的链表分割
示例:
思路:给一个头head和一个尾tail,<x值的头插,>=x值的尾插即可实现。毕竟不要求相对顺序。只要求<x的节点在前面,>=x的节点在后面即可。
并且既要头插又要尾插的话就不建议创建一个头结点了,因为夹在中间,他还没用,会造成妨碍。
#include<stdio.h>
#include<stdlib.h>struct ListNode
{int val;struct ListNode* next;
};
struct ListNode* partition(struct ListNode* phead, int x)
{struct ListNode* head = NULL, * tail = NULL;struct ListNode* cur = phead,* prev = NULL;while (cur){if (cur->val < x){//头插要判断,如果是在中间头插,先要保存cur的下一个节点的地址才行if (head == NULL){head = tail = cur;cur = cur->next;}else{prev = cur->next;cur->next = head;head = cur;cur = prev;}}else{//尾插就不需要考虑太多了if (head == NULL){head = tail = cur;}else{tail->next = cur;tail = cur;}cur = cur->next;}}return head;
}
int main()
{struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));int k = 5;n1->val = 1;n2->val = 2;n3->val = 4;n4->val = 3;n5->val = 9;n1->next = n2;n2->next = n3;n3->next = n4;n4->next = n5;n5->next = NULL;struct ListNode* obj = partition(n1, k);while (obj){printf("%d", obj->val);obj = obj->next;}return 0;
}