LeetCode 86. Partition List

86. Partition List

Difficulty:: Medium

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

Solution

Language: Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *       int val;
 *       ListNode next;
 *       ListNode(int x) { val = x; }
 * }
 */
class Solution {
      public ListNode partition(ListNode head, int x) {
            if (head == null) {
                  return null;
           }
            ListNode less = new ListNode(0);
            ListNode lessEnd = less;
            ListNode large = new ListNode(0);
            ListNode largeEnd = large;
            while (head != null) {
                  if (head.val < x) {
                        lessEnd.next = head;
                        lessEnd = head;
                 } else {
                        largeEnd.next = head;
                        largeEnd = head;
                 }
                  head = head.next;
           }
            lessEnd.next = large.next;
            largeEnd.next = null;
            return less.next;
     }
}