86. Partition List

题意:

给出一个链表和一个数字M, 将这个链表划分为两个链表.
第一个链表是小于数字M的部分, 第二个链表是大于等于数字M的部分.
第一个链表排在第二个链表前面.
如给出:1->4->3->2->5->2 和3
返回 1->2->2->4->3->5
需要保证原链表中数字的相对位置不能改变.

解法1:

大体的思路就是通过构造两个链表再将这两个链表首尾相连.
不难想到, 这两个链表可能会有一个链表为空, 按正常实现方式来做可能就比较麻烦.
下面这种做法就是需要手动判断是否有一个链表为空, 情况比较复杂.

    ListNode* partition(ListNode* head, int x) {
        if (!head)
            return head;

        ListNode *p = head;
        ListNode *lesshead, *less, *greaterhead, *greater;

        lesshead = NULL;
        greaterhead = NULL;
        less = NULL;
        greater = NULL;

        while (p){
            if (p->val < x) {
                if (!lesshead)
                {
                    lesshead = p;
                    less = lesshead;
                }
                else{ 
                    less->next = p;
                    less = less->next;
                }
            }
            else {
                if (!greaterhead)
                { 
                    greaterhead = p;
                    greater = greaterhead;
                }
                else{
                    greater->next = p;
                    greater = greater->next;
                }
            }
            p = p->next;
        }
        if(greater)
            greater->next = NULL;
        if(less)
            less->next = greaterhead;
        return lesshead?lesshead:greaterhead;
    }

解法2:

这个解法是Solution里面提供的方法, 为两个新链表分别加一个空的头指针.
并且通过引用(别名)的方式为两个链表进行插值.

    ListNode* partition(ListNode* head, int x) {
        ListNode *l = new ListNode(0);
        ListNode *r = new ListNode(0);

        ListNode *left = l;
        ListNode *right = r;
        while (head){
            ListNode* &ref = head->val >= x ? r : l; // 根据情况成为左右两个链表指针的别名;
            ref->next = head;

            ref = ref->next;
            head = head->next;
        }

        l->next = right->next; // l, r最后都会指向最后一个元素
        r->next = NULL;
        return left->next;
    }