InterviewBit Academy is now Scaler!
Learn Tech Skills from Scratch @ Scaler EDGE

Sort Binary Linked List


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

Return the head pointer of the new sorted linked list.



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.
Start solving Sort Binary Linked List on Interview Code Editor
Hints
  • Hint 1
  • Solution Approach
  • Complete Solution
Asked In:

Discussion


Loading...
Click here to start solving coding interview questions