目录
题目要求
手搓简易单链表
代码实现
题目要求
现有一链表的头指针 ListNode* head ,给一定值 x ,编写一段代码将所有小于 x 的节点排在其余节点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头节点
举例说明:
输入:x = 5 ; [1,3,9,6,5,4,7,2]
输出:[1,3,4,2,9,6,5,7]
手搓简易单链表
代码演示:
struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n1);
struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n2);
struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n3);
struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n4);
struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n5);
struct ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n6);
struct ListNode* n7 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n7);
struct ListNode* n8 = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(n8);
n1->val = 1;
n2->val = 3;
n3->val = 9;
n4->val = 6;
n5->val = 5;
n6->val = 4;
n7->val = 7;
n8->val = 2;
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = n6;
n6->next = n7;
n7->next = n8;
n8->next = NULL;
代码实现
代码演示:
struct ListNode* partition(struct ListNode* head, int x)
{
// 小于 x 的头尾节点
struct ListNode* lesshead;
struct ListNode* lesstail;
// 大于等于 x 的头尾节点
struct ListNode* greaterhead;
struct ListNode* greatertail;
// 定义哨兵位
lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur = head;
while (cur != NULL)
{
if (cur->val < x)
{
lesstail->next = cur;
lesstail = lesstail->next;
}
else
{
greatertail->next = cur;
greatertail = greatertail->next;
}
cur = cur->next;
}
// 链接两个链表
lesstail->next = greaterhead->next;
greatertail->next = NULL;
head = lesshead->next;
free(lesshead);
free(greaterhead);
return head;
}
代码解析:
代码思路:创建两个带哨兵位的单链表,一个用来链接小于 x 的节点,一个用来链接大于等于 x 的节点,最后再把两个链表进行链接,这样就完成了链表的分割,并且没有改变原来的数据顺序
代码逻辑:lesshead 和 lesstail 用来管控小于 x 的节点,lesshead 是哨兵位,不存储有效数据,lesstail 向后链接小于 x 的节点,greaterhead 和 greatertail 作用同上,是用来链接大于等于 x 的节点,进行分割后,不要忘记将 greatertail 的 next 置空,因为分割后 greatertail 节点不一定是为节点,最后再将 lesshead 哨兵位的 next 赋值给 head ,再释放,即可
代码验证:
算法的时间和空间复杂度:
while 循环执行了 N 次,每次内部常数次,只 malloc 开辟了两个节点,可忽略不计
算法的时间复杂度:O(N)
算法的空间复杂度:O(1)