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 }
执行结果如下: