Leetcode: Partition List

This question is asked at Amazon, Microsoft, Apple, and Facebook. It is as follows: 

GIven the head of 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. 

This problem wants us to reform the linked list structure such that the elements lesser than a certain value x come before the elements greater than x. If we break the linked list at the joint, we get 2 smaller linked lists. Our main goal is to create these two linked lists and join them.

Here are is an example of an input and an output: 

Input: head = [1,4,3,2,5,2], x = 3

Output: [1,2,2,4,3,5]

Notice that the values less than 3 are all on the left of the list. 

We take 2 pointers, before and after, to keep track of the linked lists, and used to keep 2 separate linked lists. The algorithm is as follows: 

We first initialize 2 pointers, before and after, and in the implementation, we initialized these 2 two with dummy values.

We iterate through the original list. If the node's value pointer by head is lesser than x the node should be part of the before list, else, the node should be part of the after list. Finally, we combine the lists together. 

Here's the final code: 

class Solution {

    public ListNode partition(ListNode head, int x) {

        ListNode before_head = new ListNode(0);

        ListNode before = before_head;

        ListNode after_head = new ListNode(0);

        ListNode after = after_head;

        while(head != null) {

            //add less than left values to the left hand side of the list. 

            if(head.val < x) {

                before.next = head;

                before = before.next;

            } else {

                //put in the after list

                after.next = head;

                after = after.next;

            }

            //move through original list

            head = head.next;

        }

        after.next = null;

        //join lists together

        before.next = after_head.next;

        return before_head.next;

    }

}