Merge Sort on Doubly Linked List

Medium Accuracy: 60.43% Submissions: 9631 Points: 4

Given Pointer/Reference to the head of a doubly linked list of N nodes, the task is to Sort the given doubly linked list using Merge Sort in both non-decreasing and non-increasing order.

Example 1:

Input:
N = 8
value[] = {7,3,5,2,6,4,1,8}
Output:
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
Explanation: After sorting the given
linked list in both ways, resultant
matrix will be as given in the first
two line of output, where first line
is the output for non-decreasing
order and next line is for non-
increasing order.

Example 2:

Input:
N = 5
value[] = {9,15,0,-1,0}
Output:
-1 0 0 9 15
15 9 0 0 -1
Explanation: After sorting the given
linked list in both ways, the
resultant list will be -1 0 0 9 15
in non-decreasing order and 
15 9 0 0 -1 in non-increasing order.

Your Task:
The task is to complete the function sortDoubly() which sorts the doubly linked list. The printing is done automatically by the driver code.



#User function Template for python3


'''

class Node:

def __init__(self, data):

self.data = data

self.next = None

self.prev = None


'''

#Function to sort the given doubly linked list using Merge Sort.

def split(head):

 

    slow = head

    fast = head.next

 

    # Advance 'fast' by two nodes, and advance 'slow' by single node

    while fast:

        fast = fast.next

        if fast:

            slow = slow.next

            fast = fast.next

 

    return slow

 

 

# Recursive function to merge nodes of two sorted lists together

# into a single sorted list

def merge(a, b):

 

    # Base cases

    if a is None:

        return b

 

    if b is None:

        return a

 

    # Pick either a or b, and recur

    if a.data <= b.data:

        a.next = merge(a.next, b)

        a.next.prev = a

        a.prev = None

        return a

    else:

        b.next = merge(a, b.next)

        b.next.prev = b

        b.prev = None

        return b

 

 

# Function to sort a doubly linked list using merge sort algorithm

def sortDoubly(head):

 

    # base case: 0 or 1 node

    if head is None or head.next is None:

        return head

 

    # split head into 'a' and 'b' sublists

    a = head

 

    slow = split(head)

    b = slow.next

    slow.next = None

 

    # recursively sort the sublists

    a = sortDoubly(a)

    b = sortDoubly(b)

 

    # merge the two sorted lists together

    head = merge(a, b)

    return head

Comments

Post a Comment

Popular posts from this blog

Large Factorial of array

You are given an array   A   of integers of length   N . You need to calculate factorial of each number. The answer can be very large, so print it modulo   10 9  + 7 .   Example 1: Input: N = 5 A[] = {0, 1, 2, 3, 4} Output: 1 1 2 6 24 Explanation: Factorial of 0 is 1, factorial of 1 is 1, factorial of 2 is 2,  factorial of 3 is 6 and so on. Example 2: Input: N = 3 A[] = {5, 6, 3} Output: 120 720 6 Explanation: Factorial of 5 is 120, factorial of 6 is 720,  factorial of 3 is 6. Your Task: Complete the function  factorial()  which takes   list  a  and single integer  n , as input parameters and returns a list of factorials of the numbers in the list a.
Read more

LEARN SOMMETHING INTRESTING

  Yeah, I love Python one-liners. Let us break it down. input()   This is used to fetch input from the user. In this case. We are expecting the user to provide a list of integers. How do I know? Look next. input().strip()   This will eliminate trailing spaces from the user input, if they are there. Why is it required? Because some users will do that and that might break your program. Remember that input() will cast the input as string. So, now we have a string of integers like so: “1 2 4 42” input.strip().split()   split() is used to create a Python list out of a string. If no delimiter is given, this breaks the string by spaces. So, now we have: [“1”, “2”, “4”, “42”] map(int, input().strip().split())   map() takes two arguments. The first one is the method to apply, the second one is the data to apply it to. By this understanding, we can see this is doing nothing but typecasting every element of the list to an integer value. Since map returns the data type it w...
Read more

Value equal to index value

Given an array   Arr   of   N   positive integers. Your task is to find the elements whose value is equal to that of its index value. Example 1: Input: N = 5 Arr[] = {15, 2, 45, 12, 7} Output: 2 Explanation: Only Arr[2] = 2 exists here. Example 2: Input: N = 1 Arr[] = {1} Output: 1 Explanation: Here Arr[1] = 1 exists. Your Task:   You don't need to read input or print anything. Your task is to complete the function  valueEqualToIndex()  which takes the array of integers  arr[]   and  n  as parameters and returns an array of indices where the given conditions are satified. When there is not such element exists then return an empty array of length 0. Expected Time Complexity:  O(N) Expected Auxiliary Space:  O(1) Note : There can be more than one element in the array which have same value as their index. You need to include every such element's index. Follows 1-based indexing of the array. Constraints: ...
Read more