leetcode筆記：Partition List

一. 題目描述

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

二. 題目分析

題目的大意是，給定一個單鏈表和一個值x，把鏈表中小於x的放到x的前面，大於等於x的放到x的後面，每部分元素的原始相對位置不變。

該題是一個普通的鏈表遍歷的題目，需要注意的地方在於必須將鏈表的最後一個節點的下一個節點更新為null，不然鏈表會出現環，從而導致死循環的情況。

三. 示例代碼

#include 

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};


class Solution
{
public:
    ListNode *partition(ListNode *head, int x)
    {
        ListNode *LessHeader = new ListNode(10);
        ListNode *LessTail = LessHeader;

        ListNode *GreaterHeader = new ListNode(10);
        ListNode *GreaterTail = GreaterHeader;

        while(head != NULL)
        {
            if (head->val < x)
            {
                LessTail->next = head;
                LessTail = head;
            }
            else
            {
                GreaterTail->next = head;
                GreaterTail = head;
            }

            head = head->next;
        }

        LessTail->next = GreaterHeader->next;
        GreaterTail->next = NULL;
        delete GreaterHeader;

        head = LessHeader->next;
        delete LessHeader;

        return head;
    }
};

四. 小結

無