Sort Linked List
You are given a Singly Linked List of integers which is sorted based on absolute value.

You have to sort the Linked List based on actual values.

The absolute value of a real number x, denoted |x|, is the non-negative value of x without regard to its sign.

Example:

If the given list is {1 - -2 - 3} (which is sorted on absolute value), the returned list should be {-2 - 1 - 3}.

Input Format:

The first line of input contains a single integer ‘T’, representing the number of test cases or queries to be run. Then the T test cases follow. The first line of each test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element. It is guaranteed that the given list is sorted based on absolute value.

Output Format:

For each test case, print the sorted linked list. The elements of the sorted list should be single-space separated, terminated by -1. The output of each test case is printed in a separate line.

Note :

You don't need to print the output, it has already been taken care of. Just implement the given function.

Constraints :

1

Question

Sort Linked List

You are given a Singly Linked List of integers which is sorted based on absolute value.

You have to sort the Linked List based on actual values.

The absolute value of a real number x, denoted |x|, is the non-negative value of x without regard to its sign.

Example:

If the given list is {1 -> -2 -> 3} (which is sorted on absolute value), the returned list should be {-2 -> 1 -> 3}.

Input Format:

The first line of input contains a single integer ‘T’, representing the number of test cases or queries to be run. Then the T test cases follow.

The first line of each test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

It is guaranteed that the given list is sorted based on absolute value.

Output Format:

For each test case, print the sorted linked list. The elements of the sorted list should be single-space separated, terminated by -1.

The output of each test case is printed in a separate line.

Note :

You don't need to print the output, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= 'N' <= 5 * 10^4
-10^9 <= 'data' <= 10^9 and 'data' != -1

Where 'N' denotes the number of elements in the Singly Linked List and 'data' represents the value of those elements.

Time Limit : 1 sec

Accepted Answer

Use 2 pointers: fast and slow to divide the list into 2 sublist: list1 and list2 and make sure list1 is equal to or is longer than list2.
The key is the condition of while loop while(fast.next!=null && fast.next.next!=null). After this while loop slow will be at the position of the end of list1.
sort list1 and list2
merge list1 and list2

Accepted Answer

Insertion Sort

We will use the ‘Insertion Sort’ algorithm to sort the given linked list.

Algorithm:

We will make a list ‘SORTED_LIST’ which is initially empty and it stores the list after sorting.

We will traverse the given list and insert the node in the ‘SORTED_LIST’ such that nodes are present in sorted order.

For each node follow these steps:

If ‘SORTED_LIST’ is empty or the head of the ‘SORTED_LIST’ has a value greater than the node, in this case, the current node will become the new head of ‘SORTED_LIST’.
Else, we will traverse the ‘SORTED_LIST’ until we find the node that has a value greater than the current node or until we reach the end.
We will insert the node at this position and change it’s ‘next’ value such that it points to the node which is greater than the current node.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the linked list.

As O(N) additional space is required to store the ‘SORTED_LIST’.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the number of nodes in the linked list.

In the worst case, it takes O(N) time to insert the node in ‘SORTED_LIST’, and traversing the list takes O(N) time. Thus, the final time complexity is O(N ^ 2).

Python (3.5)

'''

    Time Complexity: O(N ^ 2)

    Space complexity: O(N)

    

    Where N is the number of nodes in the linked list.   

'''



def sortLL(head):

    sortedList = None



    while (head != None):

        ahead = head.next



        # This node will be the head of sortedList.

        if (sortedList == None or head.data < sortedList.data):

            head.next = sortedList

            sortedList = head



        else:

            cur = sortedList



            # Traversing the sorted list.

            while (cur.next != None and cur.next.data < head.data):

                cur = cur.next



            temp = cur.next

            cur.next = head

            head.next = temp



        head = ahead



    return sortedList

Java (SE 1.8)

/*

    Time Complexity: O(N ^ 2)

    Space complexity: O(N)

    

    Where 'N' is the number of nodes in the linked list.

*/



public class Solution {



    public static Node sortLL(Node head) {

        Node sortedList = null;



        while (head != null) {

            Node ahead = head.next;



            // This node will be the head of sortedList.

            if (sortedList == null || head.data < sortedList.data) {

                head.next = sortedList;

                sortedList = head;

            } else {

                Node cur = sortedList;

                

                // Traversing the sorted list.

                while (cur.next != null && cur.next.data < head.data) {

                    cur = cur.next;

                }



                Node temp = cur.next;

                cur.next = head;

                head.next = temp;

            }



            head = ahead;

        }

        return sortedList;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N ^ 2)

    Space complexity: O(N)

    

    Where N is the number of nodes in the linked list.

*/



Node *sortLL(Node *head)

{

    Node *sortedList = NULL;



    while (head != NULL)

    {

        Node *ahead = head->next;



        // This node will be the head of sortedList.

        if (sortedList == NULL || head->data < sortedList->data)

        {

            head->next = sortedList;

            sortedList = head;

        }

        else

        {

            Node *cur = sortedList;

            // Traversing the sorted list.

            while (cur->next != NULL && cur->next->data < head->data)

            {

                cur = cur->next;

            }

            Node *temp = cur->next;

            cur->next = head;

            head->next = temp;

        }



        head = ahead;

    }

    return sortedList;

}

Accepted Answer

Merge Sort

We will use the ‘Merge Sort’ algorithm to sort the given linked list. Merge Sort is a Divide and Conquer algorithm. In this algorithm, we will divide the list into two parts, recursively sort the two parts and finally merge them such that the resultant list will be sorted.

Algorithm:

If the list contains only one node, return the head of the list.
Else, divide the list into two sublists. For this, we will take pointers ‘MID’ and ‘TAIL’ which will initially point to the head node. We will change ‘MID’ and ‘TAIL’ as follows until ‘TAIL’ becomes NULL:
- ‘MID = MID->next'
- ‘TAIL = TAIL->next->next’
The above operation will ensure that mid will point to the middle node of the list. ‘MID’ will be the head of the second sublist, so we will change the ‘next’ value of the node which is before mid to NULL.
Call the same algorithm for the two sublists.
Merge the two sublists and return the head of the merged list. For this, we will make a list ‘MERGE_LIST’ which will be initially empty. If the head of the first sublist has a value less than the head of the second sublist then we will add the head of the first sublist in the ‘MERGE_LIST’ and change the head to its next value. Else, we will add the head of the second sub list. In the end, if any of the sublists becomes empty and the other sublist is non-empty, then we will add all nodes of the non-empty sublist in the ‘MERGE_LIST’.

Space Complexity: O(logn)Explanation:

O(log(N)), where N is the number of nodes in the linked list

Since the algorithm is recursive and there are log(N) levels, it requires O(log(N) ) stack space.

Time Complexity: O(nlogn)Explanation:

O(N * log(N)), where N is the number of nodes in the linked list.

The algorithm used (Merge Sort) is divide and conquer. So, for each traversal, we divide the list into 2 parts, thus there are log(N) levels and the final complexity is O(N * log(N)).

C++ (g++ 5.4)

/*

    Time Complexity: O(N * log(N))

    Space complexity: O(log(N))

    

    Where N is the number of nodes in the linked list.

*/



Node *merge(Node *firstHead, Node *secondHead)

{

    Node *mergeList = NULL, *cur = NULL;



    while (firstHead != NULL && secondHead != NULL)

    {

        if (firstHead->data < secondHead->data)

        {

            if (mergeList == NULL)

            {

                mergeList = firstHead;

                cur = firstHead;

            }

            else

            {

                cur->next = firstHead;

                cur = cur->next;

            }

            firstHead = firstHead->next;

        }

        else

        {

            if (mergeList == NULL)

            {

                mergeList = secondHead;

                cur = secondHead;

            }

            else

            {

                cur->next = secondHead;

                cur = cur->next;

            }

            secondHead = secondHead->next;

        }

    }



    if (firstHead != NULL)

    {

        cur->next = firstHead;

    }

    if (secondHead != NULL)

    {

        cur->next = secondHead;

    }



    return mergeList;

}



Node *sortLLHelper(Node *head)

{

    if (head == NULL || head->next == NULL)

    {

        return head;

    }



    // dividing list into two sublists

    Node *mid = head, *tail = head, *prev;

    while (tail != NULL && tail->next != NULL)

    {

        prev = mid;

        mid = mid->next;

        tail = tail->next->next;

    }

    prev->next = NULL;



    Node *firstHead = head;

    Node *secondHead = mid;



    // calling the recursive function on sublists

    firstHead = sortLLHelper(firstHead);

    secondHead = sortLLHelper(secondHead);



    head = merge(firstHead, secondHead);



    return head;

}



Node *sortLL(Node *head)

{

    head = sortLLHelper(head);

    return head;

}

Python (3.5)

'''

    Time Complexity: O(N * log(N))

    Space complexity: O(log(N))

    

    Where N is the number of nodes in the linked list.   

'''



def merge(firstHead, secondHead):

    mergeList, cur = None, None



    while (firstHead != None and secondHead != None):

        if (firstHead.data < secondHead.data):

            if (mergeList == None):

                mergeList = firstHead

                cur = firstHead



            else:

                cur.next = firstHead

                cur = cur.next



            firstHead = firstHead.next

        else:

            if (mergeList == None):

                mergeList = secondHead

                cur = secondHead



            else:

                cur.next = secondHead

                cur = cur.next

            secondHead = secondHead.next



    if (firstHead != None):

        cur.next = firstHead



    if (secondHead != None):

        cur.next = secondHead



    return mergeList



def sortLLHelper(head):

    if (head == None or head.next == None):

        return head



    # Dividing list into two sublists.

    mid, tail = head, head

    prev = None



    while (tail != None and tail.next != None):

        prev = mid

        mid = mid.next

        tail = tail.next.next



    prev.next = None



    firstHead = head

    secondHead = mid



    # Calling the recursive function on sublists.

    firstHead = sortLLHelper(firstHead)

    secondHead = sortLLHelper(secondHead)



    head = merge(firstHead, secondHead)



    return head



def sortLL(head):

    head = sortLLHelper(head)

    return head

Java (SE 1.8)

/*

    Time Complexity: O(N * log(N))

    Space complexity: O(log(N))

    

    Where N is the number of nodes in the linked list.

*/



public class Solution {



    public static Node merge(Node firstHead, Node secondHead) {

        Node mergeList = null, cur = null;



        while (firstHead != null && secondHead != null) {

            if (firstHead.data < secondHead.data) {

                if (mergeList == null) {

                    mergeList = firstHead;

                    cur = firstHead;

                } else {

                    cur.next = firstHead;

                    cur = cur.next;

                }

                firstHead = firstHead.next;

            } else {

                if (mergeList == null) {

                    mergeList = secondHead;

                    cur = secondHead;

                } else {

                    cur.next = secondHead;

                    cur = cur.next;

                }

                secondHead = secondHead.next;

            }

        }



        if (firstHead != null) {

            cur.next = firstHead;

        }



        if (secondHead != null) {

            cur.next = secondHead;

        }



        return mergeList;

    }



    public static Node sortLLHelper(Node head) {

        if (head == null || head.next == null) {

            return head;

        }



        // Dividing list into two sublists.

        Node mid = head, tail = head, prev = null;

        while (tail != null && tail.next != null) {

            prev = mid;

            mid = mid.next;

            tail = tail.next.next;

        }

        prev.next = null;



        Node firstHead = head;

        Node secondHead = mid;



        // Calling the recursive function on sublists.

        firstHead = sortLLHelper(firstHead);

        secondHead = sortLLHelper(secondHead);



        head = merge(firstHead, secondHead);



        return head;

    }



    public static Node sortLL(Node head) {

        head = sortLLHelper(head);

        return head;

    }

}

Accepted Answer

Reverse negative values

In the given list all non-negative values are present in sorted order but all negative values are present in reverse order. We have to reverse the negative values and move it before the first non-negative value.

For example, say the given list is {0-> 1 -> -2 -> 3 -> -4}. In this list, non-negative values {0, 1, 3} are present in sorted order and the negative values {-2, -4} are present in reverse order.

So, we traverse the list and if we encounter a negative value node, we will move this node before the head node and this node will become the new head of the list. After doing this for all negative values, we will have a sorted list.

Space Complexity: O(1)Explanation:

O(1).

Constant additional space is required. Thus, the final space complexity is O(1).

Time Complexity: O(n)Explanation:

O(N), where N is the number of nodes in the linked list.

We are considering each node in the list exactly once, thus the final time complexity is O(N).

Python (3.5)

'''

    Time Complexity: O(N)

    Space complexity: O(1)

    

    Where N is the number of nodes in the linked list.

'''



def sortLL(head):



    cur = head.next

    prev = head

    while (cur != None):



        # If node has a negative value.

        if (cur.data < 0):



            prev.next = cur.next

            cur.next = head

            head = cur

            cur = prev



        prev = cur

        cur = cur.next



    return head

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space complexity: O(1)

    

    Where N is the number of nodes in the linked list.

*/



public class Solution {



    public static Node sortLL(Node head) {

        Node cur = head.next, prev = head;



        while (cur != null) {



            // If node has a negative value.

            if (cur.data < 0) {

                prev.next = cur.next;

                cur.next = head;

                head = cur;

                cur = prev;

            }

            prev = cur;

            cur = cur.next;

        }

        return head;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space complexity: O(1)

    

    Where N is the number of nodes in the linked list.

*/



Node *sortLL(Node *head)

{

    Node *cur = head->next, *prev = head;

    

    while (cur != NULL)

    {

        // If node has a negative value.

        if (cur->data < 0)

        {

            prev->next = cur->next;

            cur->next = head;

            head = cur;

            cur = prev;

        }

        prev = cur;

        cur = cur->next;

    }

    return head;

}

You are given a Singly Linked List of integers which is sorted based on absolute value.

You have to sort the Linked List based on actual values.

The absolute value of a real number x, denoted |x|, is the non-negative value of x without regard to its sign.

Example:

Input Format:

Output Format:

Note :

Constraints :

Algorithm:

Top Freshworks Software Engineer interview questions & answers

Popular interview questions of Software Engineer