2021-03-17：手写代码：单链表插入排序。
16lz
2021-03-17
2021-03-17：手写代码：单链表插入排序。
福大大 答案2021-03-17：
从链表的第二个节点开始遍历。当前节点的左边所有节点一定是有序的。先比较当前节点和左邻节点，如果左邻节点小于等于当前节点，直接下个节点；如果左邻节点大于当前节点，从链表的有序部分的第一个节点开始遍历，找到当前节点小于有序部分的某个节点，然后插入进去。
代码用golang编写，代码如下：
package mainimport "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 = InsertSort(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 InsertSort(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } preAns := &ListNode{Next: head} pre := head cur := head.Next for cur != nil { if pre.Val <= cur.Val { //不管 //下一个循环的准备工作 pre, cur = cur, cur.Next } else { preTemp := preAns temp := preAns.Next for cur.Val >= temp.Val { preTemp, temp = temp, temp.Next } //删除当前节点 pre.Next = cur.Next //有序节点里插入当前节点 preTemp.Next, cur.Next = cur, temp //下一个循环的准备工作，pre不变 cur = pre.Next } } return preAns.Next}执行结果如下：
力扣148. 排序链表
评论
好知识，才能预见未来
赞赏
0人进行了赞赏支持
更多相关文章
- Kafka单节点至集群的安装部署及注意事项
- 循环单链表及常用操作（C语言描述）
- 云服务让HPC死而复生
- es软件安装
- 还在浪费资源“海推”产品？这个银行产品推荐系统你必须知道！（附教程
- 1.2 Ansible 基础概念
- 算法基础7：平衡查找树概述
- 2021-03-15：手写代码：单链表选择排序。
- ZooKeeper原理详解及常用操作