leetcode 86 分隔链表 / partition list
程序员文章站
2022-05-12 09:17:26
...
题目描述:
又是关于链表的操作题,感觉自己做这类题比较缺乏经验,想到哪写到哪,代码原没有别人简洁明了,还需要多多学习。
参考代码:
/**
* 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 dummy1(-1),dummy2(-1);
ListNode *root1=&dummy1,*root2=&dummy2;
while(head){
if(head->val<x){
root1->next=head;
head=head->next;
root1=root1->next;
root1->next=NULL;
}
else{
root2->next=head;
head=head->next;
root2=root2->next;
root2->next=NULL;
}
}
root1->next=dummy2.next;
return dummy1.next;
}
};
我的:
/**
* 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) {
if(head == NULL) return head;
ListNode* q = head;
ListNode* temp;
int total = 1;
while(q -> next != NULL){
total += 1;
q = q -> next;
} // q记录最后一个节点
ListNode* p = head;
int cnt = 0;
while(p -> val >= x && cnt < total){ // 找到第一个小于x的节点
temp = p;
q -> next = temp;
p = p -> next;
temp -> next = NULL;
q = temp;
cnt += 1;
}
if(cnt > total) return p;
cnt += 1;
if(cnt == total) return p;
ListNode* begin = p;
while(cnt < total){
if(p -> next != NULL && p -> next -> val < x){
p = p -> next;
cnt += 1;
}
else if(p -> next != NULL && p -> next -> val >= x){
temp = p -> next;
q -> next = temp;
p -> next = p -> next -> next;
temp -> next = NULL;
q = temp;
cnt += 1;
}
}
return begin;
}
};
推荐阅读
-
Leetcode0143--Reorder List 链表重排
-
leetcode第86. 分隔链表C++
-
C++实现LeetCode(86.划分链表)
-
LeetCode 114.Flatten Binary Tree to Linked List (二叉树展开为链表)
-
leetcode 86 分隔链表 / partition list
-
leetcode 206 反转链表 / reverse linked list
-
Leetcode0143--Reorder List 链表重排
-
【leetcode】114. 二叉树展开为链表(Flatten Binary Tree to Linked List)(DFS)
-
【反转链表模板题+迭代+递归】LeetCode 206. Reverse Linked List
-
【小白爬Leetcode19】1.11 删除链表的倒数第N个节点 Remove Nth Node From End of List