中山 在门户网站推广,wordpress 标签绑定二级域名,网络舆情监测 toom,蓬莱做网站公司题目描述#xff1a;
链表分割_牛客题霸_牛客网 (nowcoder.com) 现有一链表的头指针 ListNode* pHead#xff0c;给一定值x#xff0c;编写一段代码将所有小于x的结点排在其余结点之前#xff0c;且不能改变原来的数据顺序#xff0c;返回重新排列后的链表的头指针。 题解…题目描述
链表分割_牛客题霸_牛客网 (nowcoder.com) 现有一链表的头指针 ListNode* pHead给一定值x编写一段代码将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针。 题解思路 分别创建两个新链表 less、large并用一个指针current指向原始链表的头节点用于遍历这里位于后续尾插可以使用带哨兵位头节点的链表和尾指针指向两链表的尾端比较current指向节点的值与给定值x的大小关系如果current节点的值小于x将current的值作为新节点的值尾插到 less 头节点的后面移动current如果current节点的值大于、等于x将current的值作为新节点的值尾插到 large 头节点的后面移动 current重复步骤二直到current遍历所有节点指向NULL连接 less 和 large 用 less 的尾指针的指针域指向 large 头节点的下一个返回 less 头结点的下一个。 代码
ListNode* partition(ListNode* pHead, int x) {struct ListNode* lessHead (ListNode*)malloc(sizeof(ListNode));struct ListNode* largeHead (ListNode*)malloc(sizeof(ListNode));lessHead-next NULL;largeHead-next NULL;struct ListNode* lessTail lessHead;struct ListNode* largeTail largeHead;struct ListNode* current pHead;while(current){// 比较if(current-val x){// 尾插struct ListNode* newNode (ListNode*)malloc(sizeof(ListNode));newNode-next NULL;newNode-val current-val;lessTail-next newNode;lessTail newNode;}else {struct ListNode* newNode (ListNode*)malloc(sizeof(ListNode));newNode-next NULL;newNode-val current-val;largeTail-next newNode;largeTail newNode;}current current-next;}// 连接lessTail-next largeHead-next;return lessHead-next;} 注这里尾插的的时候可以不进行创建新的节点可以直接用原链表的节点进行连接即可。
ListNode* partition(ListNode* pHead, int x){struct ListNode* lessHead, *lessTail , *largeHead, *largeTail, *current;lessHead lessTail (struct ListNode*)malloc(sizeof(struct ListNode));largeHead largeTail (struct ListNode*)malloc(sizeof(struct ListNode));lessTail-next NULL;largeTail-next NULL;current phead;while (current ! NULL){if (current-val x){lessTail-next current ;lessTail current ;}else{largeTail-next current ;largeTail current ;}current current-next;}lessTail-next largeHead-next;ListNode* temp lessHead-next;free(lessHead);free(largeHead);return temp;
} 显然这种方法更好但其思路是一模一样的。 本次内容到此结束了如果你觉得这篇博客对你有帮助的话 希望你能够给我点个赞鼓励一下我。感谢感谢……
