86. Partition List ------------M

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.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

A:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode less(0);
        ListNode greater(0);
        ListNode *pl = &less;
        ListNode *pg = &greater;
        
        while(head){
            ListNode *ptr = head;
            head = head->next;
            ptr->next = nullptr;
            if(ptr->val < x){
                pl->next = ptr;
                pl = ptr;
            }else{
                pg->next = ptr;
                pg = ptr;
            }
        }
        pl->next = greater.next;
        return less.next;
    }
};

Mistakes:
1: detach 一个node， 并将之放到新的list的tail上时，， 忘记把它的next节点设为null

2: 由于命名的原因（更主要的是，开始没有思考清楚，导致） 最后把tail.next = header 了。


 --------第二遍， ---思路同上----------
 Mistakes:
1：    lowerTail.next = higherHeader.next;  刚开始，SB了，写成lowerHeader.next = higherHeader.next;


--------------3rd Pas ------------------依然是用2个header。 但是，没有用original header，而直接用head 来跑。----------------------

public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode h1 = new ListNode(0);
        ListNode h2 = new ListNode(0);
        ListNode tail1 = h1,tail2 = h2;
        while(head!= null){
            ListNode tmp = head;
            head = head.next;
            
            tmp.next = null;
            if(tmp.val<x){
                tail1.next = tmp;
                tail1 = tail1.next;
            }else{
                tail2.next = tmp;
                tail2 = tail2.next;
            }
        }
        // attach h2  to the end of h1
        tail1.next = h2.next;
        return h1.next;
    }
}

Error：
 while(head!= null){
            ListNode tmp = head;
            tmp.next = null;
            head = head.next;
          
这里，这样写，顺序是不对的。 应该先 head = head.next之后，再把tmp的指针置null