Leetcode 86. Partition List

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

/**
 * 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) {
            return head;
        }
        ListNode* left_head = nullptr;
        ListNode* right_head = nullptr;
        ListNode* left = nullptr;
        ListNode* right = nullptr;
        ListNode* current = head;
        while(current) {
            if(current->val < x) {
                if(left) {
                    left->next = current;
                    left = left->next;
                }
                else {
                    left = current;
                    left_head = left;
                }
            }
            else {
                if(right) {
                    right->next = current;
                    right = right->next;
                }
                else {
                    right = current;
                    right_head = right;
                }
            }
            current = current->next;
        }
        if(right) {
            right->next = nullptr;
        }
        if(left) {
            left->next = right_head;
            return left_head;
        }
        else {
            return right_head;
        }
    }
};

Reference

1. https://leetcode.com/problems/partition-list/description/