2021-03-16: Handwritten code: Single list merge sort.

Answer 2021-03-16:

Get the list midpoint, then split the list into two lists by midpoint. Recursively two linked lists. Merge two linked lists.

The code is written in Golang, and the code is as follows:

package main

import "fmt"

func main(a) {
    //head := &ListNode{Val: 4}
    //head.Next = &ListNode{Val: 2}
    //head.Next.Next = &ListNode{Val: 1}
    //head.Next.Next.Next = &ListNode{Val: 3}

    head := &ListNode{Val: - 1}
    head.Next = &ListNode{Val: 5}
    head.Next.Next = &ListNode{Val: 3}
    head.Next.Next.Next = &ListNode{Val: 4}
    head.Next.Next.Next.Next = &ListNode{Val: 0}

    printlnLinkNodeList(head)

    head = MergeSort(head)

    printlnLinkNodeList(head)
}

//Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

// List print
func printlnLinkNodeList(head *ListNode) {
    cur := head
    forcur ! =nil {
        fmt.Print(cur.Val, "\t")
        cur = cur.Next
    }
    fmt.Println()
}

// merge sort
func MergeSort(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    ret := process(head)
    return ret
}

// Recursively, head cannot be empty
func process(head *ListNode) *ListNode {
    // If there is only one node, return it directly
    if head.Next == nil {
        return head
    }

    // Get the midpoint
    mid := getMid(head)
    midNext := mid.Next

    // Split the list by the midpoint
    mid.Next = nil

    / / recursion
    left := process(head)
    right := process(midNext)

    / / merge
    return merge(left, right)

}

// head must not be empty
func getMid(head *ListNode) *ListNode {
    fast := head
    slow := head
    forfast.Next ! =nil&& fast.Next.Next ! =nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow
}

// merge, left and right must not be empty
func merge(left *ListNode, right *ListNode) *ListNode {
    preAns := &ListNode{}
    preAnsEnd := preAns

    forleft ! =nil&& right ! =nil {
        if left.Val <= right.Val {
            preAnsEnd.Next = left
            left = left.Next
        } else {
            preAnsEnd.Next = right
            right = right.Next
        }
        preAnsEnd = preAnsEnd.Next
    }

    if left == nil {
        preAnsEnd.Next = right
    } else {
        preAnsEnd.Next = left
    }

    return preAns.Next
}
Copy the code

The result is as follows:

Power link 148. Sort linked list comments