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

福大大架构师每日一题 · · 625 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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. 排序链表
评论


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:福大大架构师每日一题

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

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

625 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传