Leetcode 86 Solution

This article provides solution to leetcode question 86 (partition-list)
Categories:
Tags:
Access this page by simply typing in "lcs 86" in your browser address bar if you have bunnylol configured.

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

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) {
        ListNode* p1 = NULL;
        ListNode* p2 = NULL;
        ListNode* p = head;
        ListNode* p1_head = NULL;
        ListNode* p2_head = NULL;

        while (p)
        {
            if (p->val < x)
            {
                if (p1 == NULL)
                {
                    p1 = p;
                    p1_head = p;
                }
                else
                {
                    p1->next = p;
                    p1 = p;
                }
            }
            else
            {
                if (p2 == NULL)
                {
                    p2 = p;
                    p2_head = p;
                }
                else
                {
                    p2->next = p;
                    p2 = p;
                }
            }

            p = p->next;
        }

        ListNode* new_head = NULL;

        if (p1)
        {
            p1->next = p2_head;
            new_head = p1_head;
        }

        if (p2)
        {
            p2->next = NULL;

            if (new_head == NULL)
                new_head = p2_head;
        }

        return new_head;
    }
};