亲宝软件园·资讯

展开

[LeetCode] 86. Partition List

wengle 人气:0

1. 原题链接:https://leetcode.com/problems/partition-list/

2. 解题思路

  1. 从头到尾的遍历天然维护着节点之间的相对位置
  2. 采用两个链表分别记录小于x和大于等于x的节点

3. 算法

  1. left_dummy和right_dummy分别代表两个链表的哑节点
  2. 从头开始遍历链表,当节点val小于x时,更新left_dummy链表;否则,更新right_dummy链表
  3. 循环完成后,将两个链表连接起来

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;
    }
};

加载全部内容

相关教程
猜你喜欢
用户评论