2021-03-16:手写代码:单链表归并排序。

福大大架构师每日一题 发表于 2021/03/16 21:23:33 2021/03/16
【摘要】 2021-03-16:手写代码:单链表归并排序。福大大 答案2021-03-16:获取链表中点,然后按中点分成两个链表。递归两个链表。合并两个链表。代码用golang编写,代码如下:package mainimport "fmt"func main() { //head := &ListNode{Val: 4} //head.Next = &ListNode{Val: 2} ...

2021-03-16:手写代码:单链表归并排序。

福大大 答案2021-03-16:

获取链表中点,然后按中点分成两个链表。递归两个链表。合并两个链表。

代码用golang编写,代码如下:

package main

import "fmt"

func main() {
    //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
}

//链表打印
func printlnLinkNodeList(head *ListNode) {
    cur := head
    for cur != nil {
        fmt.Print(cur.Val, "\t")
        cur = cur.Next
    }
    fmt.Println()
}

//归并排序
func MergeSort(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    ret := process(head)
    return ret
}

//递归,head不可能为空
func process(head *ListNode) *ListNode {
    //如果只有1个节点,直接返回
    if head.Next == nil {
        return head
    }

    //获取中点
    mid := getMid(head)
    midNext := mid.Next

    //按中点拆分链表
    mid.Next = nil

    //递归
    left := process(head)
    right := process(midNext)

    //合并
    return merge(left, right)

}

//找中点,head一定不为空
func getMid(head *ListNode) *ListNode {
    fast := head
    slow := head
    for fast.Next != nil && fast.Next.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow
}

//合并,left和right一定都不为空
func merge(left *ListNode, right *ListNode) *ListNode {
    preAns := &ListNode{}
    preAnsEnd := preAns

    for left != 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
}

执行结果如下:
在这里插入图片描述


力扣148. 排序链表
评论

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。