Clean C# / Java based on Merge Sort


  • 0
    R

    Merge2() merges two lists iteratively.
    Merge() merges two lists recursively.
    SortList() breaks the list into two halves and do merge.

    Code Below

    public class Solution {
        public ListNode SortList(ListNode head) {
            if(head == null || head.next == null) return head;
    
            ListNode slow = head;
            ListNode fast = head;
            while(fast.next != null && fast.next.next != null)
            {
                fast = fast.next.next;
                slow = slow.next;
            }
            
            ListNode slownext = slow.next; // head of second half
            slow.next = null; // break the chain
            
            ListNode l = SortList(head);
            ListNode r = SortList(slownext);
            
            return Merge2(l, r);
        }
        
        public ListNode Merge2(ListNode l1, ListNode l2)
        {
            ListNode fake = new ListNode(0);
            
            ListNode curr = fake;
            while(l1 != null && l2 != null)
            {
                if(l1.val < l2.val)
                {
                    curr.next = l1;
                    l1 = l1.next;
                }else
                {
                    curr.next =l2;
                    l2 = l2.next;
                }
                
                curr = curr.next;
            }
            
            if(l1 != null) curr.next = l1;
            if(l2 != null) curr.next = l2;
            return fake.next;
        }
        
        public ListNode Merge(ListNode l1, ListNode l2)
        {
            if(l1 == null) return l2;
            if(l2 == null) return l1;
            
            if(l1.val < l2.val)
            {
                l1.next = Merge(l1.next, l2);
                return l1;
            }else
            {
                l2.next = Merge(l1, l2.next);
                return l2;
            }
        }
    }

Log in to reply
 

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