Golang concise solution using merge sort


  • 0

    Using recursive function, so it's not O(1) space complexity though...
    The idea is simple, just recursively divide the list to the former half and the latter half (using two pointers and delete the connection between the former and the latter).

    After it's divided into single element, then apply "merge two sorted lists" method for each pair, back to the sorted one list.

    func sortList(head *ListNode) *ListNode {
    	if head == nil || head.Next == nil {
    		return head
    	}
    	slow, fast := head, head
    	for fast.Next != nil && fast.Next.Next != nil {
    		slow, fast = slow.Next, fast.Next.Next
    	}
    
    	firstTail := slow
    	slow = slow.Next
    	firstTail.Next = nil // divide the first list and the second
    
    	first, second := sortList(head), sortList(slow)
    	return merge(first, second)
    }
    
    func merge(head1 *ListNode, head2 *ListNode) *ListNode {
    	curHead := &ListNode{}
    	tmpHead := curHead
    
    	for head1 != nil && head2 != nil {
    		if head1.Val < head2.Val {
    			curHead.Next = head1
    			head1 = head1.Next
    			curHead = curHead.Next
    		} else {
    			curHead.Next = head2
    			head2 = head2.Next
    			curHead = curHead.Next
    		}
    	}
    
    	if head1 != nil {
    		curHead.Next = head1
    	} else if head2 != nil {
    		curHead.Next = head2
    	}
    	return tmpHead.Next
    
    

Log in to reply
 

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