2021-03-15：手写代码：单链表选择排序。
福大大 答案2021-03-15：
遍历链表，找出最小元素，链表里删除最小元素，最小元素放在需要返回的链表里。
代码用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} 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}执行结果如下：
力扣148. 排序链表
评论