leetcode[87] Partition List

题目：给定一个链表和一个数x，将链表中比x小的放在前面，其他的放在后头。例如：

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

思路：

1. 再用两个node，一个指向所有小于x的，一个指向其他的，之后把两个接在一起。接在一起需要注意large是否未移动过。

/**
 * 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) 
    {
        if (head == NULL || head -> next == NULL) return head;
        ListNode *ans_small = new ListNode(0); // 存小于x的
        ListNode *ans_large = new ListNode(0); // 存不小于x的
        ans_small -> next = head;
        ans_large -> next = head;
        ListNode *small = ans_small;
        ListNode *large = ans_large;
        ListNode *cur = head;
        
        while(cur)
        {
            if (cur -> val < x)
            {
                small -> next = cur;
                small = cur;
                cur = cur -> next;
            }
            else
            {
                large -> next = cur;
                large = cur;
                cur = cur -> next;
            }
        }
        large -> next = NULL; // 这个是为了防止large指向head的时候
        small -> next = ans_large -> next;
        head = ans_small;
        delete ans_small, ans_large;
        return head -> next;
    }
};

2. 就创建一个node，这个node遇见比x小的就插入

class Solution {
public:
    ListNode *partition(ListNode *head, int x) 
    {
        if (head == NULL || head -> next == NULL) return head;
        ListNode *ans = new ListNode(0);
        ans -> next = head;
        ListNode *small = ans; // 在它的后面插入小的
        ListNode *cur = head;
        ListNode *pre = ans; // cur的前一个指针，方便插入操作
        bool flag = true; // true说明要插入的紧接着就是下一个，那就不用插入，加加就好
        while(cur != NULL)
        {
            if (cur -> val < x && small -> next == cur) // 待插入的和之前小的相邻就不用插入了
            {
                pre = pre -> next;
                cur = cur -> next;
                small = small -> next;
            }
            else if (cur -> val < x && small -> next != cur) // 不相邻，插入
            {
                ListNode *tmpnext = small -> next;
                small -> next = cur;
                small = cur;
                cur = cur -> next;
                small -> next = tmpnext;
                pre -> next = cur;
                flag = true;
            }
            else if (cur -> val >= x)
            {
                flag = false;
                cur = cur -> next;
                pre = pre -> next;
            }
        }
        head = ans;
        delete ans;
        return head -> next;
    }
};

从第二个思路中知道了原来可以判断连个node是否相等！这个之前以为不能那样判断的，原来可以用 if(node1 == node2)。多学一个知识点了。