2021-03-17:手写代码:单链表插入排序。
【摘要】 2021-03-17:手写代码:单链表插入排序。福大大 答案2021-03-17:从链表的第二个节点开始遍历。当前节点的左边所有节点一定是有序的。先比较当前节点和左邻节点,如果左邻节点小于等于当前节点,直接下个节点;如果左邻节点大于当前节点,从链表的有序部分的第一个节点开始遍历,找到当前节点小于有序部分的某个节点,然后插入进去。代码用golang编写,代码如下:package mainimp...
2021-03-17:手写代码:单链表插入排序。
福大大 答案2021-03-17:
从链表的第二个节点开始遍历。当前节点的左边所有节点一定是有序的。先比较当前节点和左邻节点,如果左邻节点小于等于当前节点,直接下个节点;如果左邻节点大于当前节点,从链表的有序部分的第一个节点开始遍历,找到当前节点小于有序部分的某个节点,然后插入进去。
代码用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 = 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
}
执行结果如下:
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)