C# Mergesort Base Solution


  • 0

    This solution takes a divide and conquer approach more specifically the Merge-sort Algorithm.

    public class Solution {
        public ListNode SortList(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode slw = head, fst = head.next.next;
            while(fst != null && fst.next != null){
                fst = fst.next.next;
                slw = slw.next;
            }
            ListNode mid = slw.next;
            slw.next = null;
            ListNode left = SortList(head);
            ListNode right = SortList(mid);
            return Merge(left,right);
        }
        
        private ListNode Merge(ListNode left, ListNode right){
            ListNode dummy = new ListNode(0);
            ListNode ws = dummy;
            while(left != null || right != null){
                if(right == null){
                    ws.next = left;
                    left = left.next;
                }else if(left == null){
                    ws.next = right;
                    right = right.next;
                }else if(left.val < right.val){
                    ws.next = left;
                    left = left.next;
                }else {
                    ws.next = right;
                    right = right.next;
                }
                ws = ws.next;
            }
            return dummy.next;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.