86. Partition List(按x分割链表)

自己的方法一

遍历链表两次

遍历链表两次
class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head==null||head.next==null)
            return head;
        int len=0;
        ListNode p=head;
        while(p!=null){
            len++;
            p=p.next;
        }
        ListNode p1=head;
        ListNode p2=head;
        ListNode p3=head;
        ListNode out=new ListNode(0);
        ListNode out1=out;
        while(p2!=null){
            if(p2.val<x){
                ListNode tmp=new ListNode(p2.val);
                out.next=tmp;
                p2=p2.next;
                out=out.next;
            }
            else
                p2=p2.next;
        }
        while(p3!=null){
            if(p3.val>=x){
                ListNode tmp=new ListNode(p3.val);
                out.next=tmp;
                p3=p3.next;
                out=out.next;
            }
            else
               p3=p3.next;
        }
        return out1.next;
}}

自己的方法二

遍历一次

class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head==null||head.next==null)
            return head;
        ListNode out = new ListNode(0);
        ListNode pre = out;
        ListNode out1 = out;
        while(head!=null){
            if(head.val<x){
                ListNode tmp = new ListNode(head.val);
                out.next = tmp;
                head = head.next;
                out = out.next;  
                pre = out;
            }
            else
                break;
        }
        while(head!=null){
            if(head.val>=x){
                ListNode tmp = new ListNode(head.val);
                out.next = tmp;
                head = head.next;
                out = out.next;
            }
            else{
                ListNode tmp = new ListNode(head.val);
                ListNode tmp1=pre.next;
                pre.next = tmp;
                tmp.next = tmp1;
                head = head.next;
                pre = pre.next;
            }
        }
        return out1.next;      
}}