CA 24 - Sort a Linked List using Merge Sort

 

Merge Sort for Linked List

Difficulty: MediumAccuracy: 74.76%Submissions: 91K+Points: 4Average Time: 30m

You are given the head of a linked list. You have to sort the given linked list using Merge Sort.

Examples:

Input:
    
Output: 10 -> 20 -> 30 -> 40 -> 50 -> 60
Explanation: After sorting the given linked list, the resultant list will be:
    
Input:
    
Output: 2 -> 5 -> 8 -> 9
Explanation: After sorting the given linked list, the resultant list will be:

Constraints:
1 ≤ number of nodes ≤ 105
0 ≤ node->data ≤ 106



MYCODE:


class Solution:

    def mergeSort(self, head):

        if not head or not head.next:

            return head


        slow, fast = head, head.next

        while fast and fast.next:

            slow = slow.next

            fast = fast.next.next


        mid = slow.next

        slow.next = None   


        left = self.mergeSort(head)

        right = self.mergeSort(mid)


        return self.merge(left, right)


    def merge(self, a, b):

        dummy = Node(0)

        t = dummy


        while a and b:

            if a.data < b.data:

                t.next = a

                a = a.next

            else:

                t.next = b

                b = b.next

            t = t.next


        t.next = a or b

        return dummy.next



explanation:


This program is done by merge sort method which is taught in class .

where there is two functions  Merge and mergesort

The merge function is done using if else conditon and swapping the numberss if it is lesser than the previous number.

The mergesort function is used for the linked list where the merge function is used to sort the numbers.

Comments

Post a Comment

Popular posts from this blog

  CA 09 - Move All Negative Elements to end Move all negative elements to end Difficulty:  Easy Accuracy:  56.24% Submissions:  174K+ Points:  2 Given an unsorted array  arr[ ]  having both negative and positive integers. The task is to place all negative elements at the end of the array without changing the order of positive elements and negative elements. Note :  Don't return any array, just in-place on the array. Examples: Input : arr[] = [1, -1, 3, 2, -7, -5, 11, 6 ] Output : [1, 3, 2, 11, 6, -1, -7, -5] Explanation: By doing operations we separated the integers without changing the order. Input : arr[] = [-5, 7, -3, -4, 9, 10, -1, 11] Output : [7, 9, 10, 11, -5, -3, -4, -1] MY CODE: class Solution: def segregateElements(self, arr): a = [] b = [] for i in arr: if i >= 0: a.append(i) else: b.append(i) temp = a + b fo...
Read more
  CA 06 - Find the Maximum and Minimum Element in the Array Min and Max in Array Input: arr[] = [1, 4, 3, 5, 8, 6] Output: [1, 8] Explanation: minimum and maximum elements of array are 1 and 8. Input: arr[] = [12, 3, 15, 7, 9] Output: [3, 15] Explanation: minimum and maximum element of array are 3 and 15. MY CODE: The min and max are the functions which shows the maximum and minimum element class Solution: class Solution: def getMinMax(self, arr): a = arr[0] # min b = arr[0] # max for c in range(1, len(arr)): d = arr[c] if d < a: a = d if d > b: b = d return [a, b]
Read more

CA 22 - Reverse a Linked List

Image
  Reverse a linked list Difficulty:  Easy Accuracy:  73.11% Submissions:  384K+ Points:  2 Average Time:  30m You are given the  head  of a singly  linked list . You have to  reverse  the linked list and return the  head  of the reversed list. Examples: Input: Output: 4 -> 3 -> 2 -> 1 Explanation: After reversing the linkedList Input: Output: 8 -> 9 -> 10 -> 7 -> 2 Explanation: After reversing the linked list Input: Output: 8 Explanation: Constraints: 1 ≤ number of nodes ≤ 10 5 1 ≤ node->data ≤ 10 5 MyCODE: class Solution:     def reverseList(self, head):         prev=None         curr=head         while curr:             n_x =curr.next             curr.next=prev             prev=curr     ...
Read more