2021-03-15:手写代码:单链表选择排序。
【摘要】 2021-03-15:手写代码:单链表选择排序。福大大 答案2021-03-15:遍历链表,找出最小元素,链表里删除最小元素,最小元素放在需要返回的链表里。代码用golang编写,代码如下:package mainimport "fmt"func main() { //head := &ListNode{Val: 4} //head.Next = &ListNode{Val: 2...
2021-03-15:手写代码:单链表选择排序。
福大大 答案2021-03-15:
遍历链表,找出最小元素,链表里删除最小元素,最小元素放在需要返回的链表里。
代码用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}
cur := head
for cur != nil {
fmt.Print(cur.Val, "\t")
cur = cur.Next
}
fmt.Println()
head = SelectSort(head)
cur = head
for cur != nil {
fmt.Print(cur.Val, "\t")
cur = cur.Next
}
fmt.Println()
}
//Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
//选择排序
func SelectSort(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
//有换头的可能,所以新增一个虚拟头节点
preAns := &ListNode{}
preAnsEnd := preAns
preHead := &ListNode{Next: head}
//选择
var pre, cur, preSel, sel *ListNode
for preHead.Next != nil {
pre, cur = preHead, preHead.Next
//默认选中第1个节点
preSel, sel = pre, cur
//选最小的,从第2个节点开始
pre, cur = cur, cur.Next
for cur != nil {
if cur.Val < sel.Val {
preSel, sel = pre, cur
}
pre, cur = cur, cur.Next
}
//选中的节点放在答案里
preAnsEnd.Next = sel
//原链表删除选中的节点
preSel.Next = sel.Next
//尾指针指向Next
preAnsEnd = preAnsEnd.Next
}
//虚拟头节点的Next指针就是需要返回的节点
return preAns.Next
}
执行结果如下:
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)