成都网站建设推荐安徽秒搜科技,小程序如何推广运营,网站设计需要那些模块,西安seo霸屏目录
题目要求
手搓简易单链表
代码实现 题目要求
现有一链表的头指针 ListNode* head #xff0c;给一定值 x #xff0c;编写一段代码将所有小于 x 的节点排在其余节点之前#xff0c;且不能改变原来的数据顺序#xff0c;返回重新排列后的链表的头节点
举例说明给一定值 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)
