LeetCode 86. 【虚节点使用】分割链表
原题链接
简单
作者:
大明湖的鱼
,
2021-01-03 10:44:55
,
所有人可见
,
阅读 293
没有太复杂,就是遍历两次,小于x的放到一条链里,大于等于x的放到一条链里,最后接起来就行了。
还是用的 哑结点,虚节点。好像声明的时候要赋值,new Listnode(0) ,不然好像会报错
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode *p_small = new ListNode(0);
ListNode *p_large = new ListNode(0);
ListNode *large_head = p_large;
ListNode *small_head = p_small;
while(head){
if(head->val < x){
p_small->next = head;
p_small = p_small->next;
}
else{
p_large->next = head;
p_large = p_large->next;
}
head = head->next;
}
p_large->next = NULL;
p_small->next = large_head->next;
return small_head->next;
}
};