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
Given 1->4->3->2->5->2->null and x = 3,
return 1->2->2->4->3->5->null.
思路
这题比较简单。做两个新的链表less和greater。过一遍现在的链表,把< x的点连到less,其他所有的连到greater。最后把less和greater连起来就行了。
Code
/** * Definition for ListNode. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { * this.val = val; * this.next = null; * } * } */ public class Solution { /** * @param head: The first node of linked list. * @param x: an integer * @return: a ListNode */ public ListNode partition(ListNode head, int x) { // write your code here if (head == null || head.next == null) { return head; } ListNode lessDummy = new ListNode(0); ListNode less = lessDummy; ListNode greaterDummy = new ListNode(0); ListNode greater = greaterDummy; ListNode curr = head; while (curr != null) { if (curr.val < x) { less.next = curr; less = less.next; } else { greater.next = curr; greater = greater.next; } curr = curr.next; } less.next = greaterDummy.next; greater.next = null; return lessDummy.next; } }