86. 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.

实现链表中的快排的partiition，将链表分成两部分，一部分大于pival，一部分小于pival

/**
 * 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 left(0), right(0);
        ListNode *l = &left, *r = &right;

        while(head){
        //此处使用指针的引用，因为后面要修改指针的值(与修改指针指向的值区分开来)
            ListNode* &ref = head->val < x ? l : r;
            ref->next = head;
            //修改指针的值，此时如果是ref == l,那么执行下面的语句就l = l->next，如果不是引用，那么l的值不会变.
            ref = ref->next;

            head = head->next;
        }
        l->next = right.next;
        r->next = NULL;
        return left.next;
    }
};

简洁易懂的方法

/**
 * 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 left(0), right(0);
        ListNode *l = &left, *r = &right;

        while(head){
            if(head->val < x){
                l->next = head;
                l = l->next;
            }else{
                r->next = head;
                r = r->next;
            }
            head= head->next;
        }
        l->next = right.next;
        r->next = NULL;
        return left.next;
    }
};