Advertisement
Guest User

Untitled

a guest
Sep 1st, 2015
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.15 KB | None | 0 0
  1. /**
  2. * Definition for ListNode.
  3. * public class ListNode {
  4. * int val;
  5. * ListNode next;
  6. * ListNode(int val) {
  7. * this.val = val;
  8. * this.next = null;
  9. * }
  10. * }
  11. */
  12. public class Solution {
  13. /**
  14. * @param head: The first node of linked list.
  15. * @param x: an integer
  16. * @return: a ListNode
  17. */
  18. public ListNode partition(ListNode head, int x) {
  19. // write your code here
  20. // idea: use two pointer to record smaller partion and larger partion elements separately
  21. if (head == null) {
  22. return null;
  23. }
  24.  
  25. ListNode leftDummy = new ListNode(0);
  26. ListNode left = leftDummy;
  27. ListNode rightDummy = new ListNode(1);
  28. ListNode right = rightDummy;
  29.  
  30. while (head != null) {
  31. if (head.val < x) {
  32. left.next = head;
  33. left = left.next;
  34. } else {
  35. right.next = head;
  36. right = right.next;
  37. }
  38. head = head.next;
  39. }
  40.  
  41. right.next = null;
  42. left.next = rightDummy.next;
  43.  
  44. return leftDummy.next;
  45. }
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement