partition-list

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.

For example,
Given1->4->3->2->5->2and x = 3,
return1->2->2->4->3->5.

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
    public ListNode partition(ListNode head, int x) {

       if(head==null)
           return null;
       ListNode smallHead=new ListNode(0);
       ListNode bigHead=new ListNode(0);
       ListNode small=smallHead;
       ListNode big=bigHead;
       ListNode p=head;
       while(p!=null){
           if(p.val>=x){
               big.next=p;
               big=big.next;
           }else{
               small.next=p;
               small=small.next;
           }
           p=p.next;
       }
       small.next=bigHead.next;
               big.next=null;//必须把后面断掉，因为原来的节点还指着后面。我这里犯错误了，没有断掉，导致报错
       return smallHead.next;

    }

}

巴特西

partition-list

最新文章

热门文章