1. 原題鏈接：https://leetcode.com/problems/partition-list/
2. 解題思路
- 從頭到尾的遍歷天然維護著節點之間的相對位置
- 采用兩個鏈表分別記錄小于x和大于等于x的節點
3. 演算法
- left_dummy和right_dummy分別代表兩個鏈表的啞節點
- 從頭開始遍歷鏈表，當節點val小于x時，更新left_dummy鏈表；否則，更新right_dummy鏈表
- 回圈完成后，將兩個鏈表連接起來
4. 實作
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode left_dummy(-1);
ListNode right_dummy(-1);
ListNode *left_cur = &left_dummy;
ListNode *right_cur = &right_dummy;
for(ListNode *cur = head; cur != NULL; cur = cur->next){
if(cur->val < x){
left_cur->next = cur;
left_cur = cur;
}else{
right_cur->next = cur;
right_cur = cur;
}
}
left_cur->next = right_dummy.next;
right_cur->next = NULL;
return left_dummy.next;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/88235.html
標籤：其他
上一篇：[LeetCode] 92. Reverse Linked List II
下一篇：計算機網路 csma/cd協議