86 Partition List

循环过一遍，遇到超过的放在一个List里面，另外的放到另一个List里面。注意使用两个假节点的技巧。

Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        aDummy = ListNode(-1)
        bDummy = ListNode(-1)
        aCur, bCur = aDummy, bDummy
        while(head):
            next = head.next
            head.next = None
            if head.val < x:
                aCur.next = head
                aCur = aCur.next
            else:
                bCur.next = head
                bCur = bCur.next
            head = next
        aCur.next = bDummy.next
        return aDummy.next

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode aDummy = new ListNode(-1);
        ListNode aPoint = aDummy;
        ListNode bDummy = new ListNode(-1);
        ListNode bPoint = bDummy;
        ListNode p = head;
        while(p != null){
            if(p.val < x){
                aPoint.next = new ListNode(p.val);
                aPoint = aPoint.next;
            }
            else{
                bPoint.next = new ListNode(p.val);
                bPoint = bPoint.next;
            }
            p = p.next;
        }
        aPoint.next = bDummy.next;
        return aDummy.next;
    }
}