  Learn Tech Skills from Scratch @ Scaler EDGE Problem Description

Given a Linked List A consisting of N nodes.

The Linked List is binary i.e data values in the linked list nodes consist of only 0's and 1's.

You need to sort the linked list and return the new linked list.

NOTE:

• Try to do it in constant space.

Problem Constraints

1 <= N <= 105

A.val = 0 or A.val = 1

Input Format

First and only argument is the head pointer of the linkedlist A.

Output Format

Example Input

Input 1:

``` 1 -> 0 -> 0 -> 1
```

Input 2:

``` 0 -> 0 -> 1 -> 1 -> 0
```

Example Output

Output 1:

``` 0 -> 0 -> 1 -> 1
```

Output 2:

``` 0 -> 0 -> 0 -> 1 -> 1
```

Example Explanation

Explanation 1:

``` The sorted linked list looks like:
0 -> 0 -> 1 -> 1
```

Explanation 2:

``` The sorted linked list looks like:
0 -> 0 -> 0 -> 1 -> 1
```

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details. Hints
• Hint 1
• Solution Approach
• Complete Solution