2021年03月17日:手写代码:单链表插入排序。

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
}

执行结果如下:

力扣148. 排序链表
评论

本文来自:简书

感谢作者:福大大架构师每日一题

查看原文:2021年03月17日:手写代码:单链表插入排序。

• 编辑
• 预览