86. 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.

Example:

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

题目

给定一个链表，一个数x,把这个链表以x分界，左边是小于x的数，右边是大于等于x的数，排完后元素的相对位置不变，只是大小分区了。

思路

最直观的想法，新建两个链表，一个存小于x的，一个存大于x的，最后再把两个链表合并。

代码

 public ListNode partition(ListNode head, int x) {
            /*
             * Input: head = 1->4->3->2->5->2, x = 3
               Output: 1->2->2->4->3->5
             */
         if (head==null||head.next==null) {
            return head;
        }
         ListNode newHeadSmall=new ListNode(-1);
         ListNode newHeadBig=new ListNode(-1);
         ListNode curSmall=newHeadSmall;
         ListNode curBig=newHeadBig;
         
         while (head!=null) {
            if (head.val<x) {//遍历head
                curSmall.next=head;//小就连到small上
                curSmall=curSmall.next;
                head=head.next;
            }else {//大就连到big上
                curBig.next=head;
                curBig=curBig.next;
                head=head.next;
            }
        }
         curBig.next=null;//最后把big结尾指向空
         curSmall.next=newHeadBig.next;//small结尾连接big
         
        return newHeadSmall.next;//返回small
         
        }