Wednesday, August 12, 2015

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->null and x = 3,
return 1->2->2->4->3->5->null.

依旧是基础题,出错的地方是第二个指针next要设为0,错在这里了。。。dummy node的题目


/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @param x: an integer
     * @return: a ListNode 
     */
    ListNode *partition(ListNode *head, int x) {
        // write your code here
        ListNode dummyA(0);
        ListNode dummyB(0);
        ListNode* a= &dummyA;
        ListNode* b= &dummyB;
        while(head){
            if (head->val<x){
                a->next=head;
                a=a->next;
            } else{
                b->next=head;
                b=b->next;
            }
            head=head->next;
        }
        b->next=NULL;
        a->next=dummyB.next;
        return dummyA.next;
    }
};

No comments:

Post a Comment