2021-03-14：手写代码：单链表冒泡排序。
原创2021-03-14：手写代码：单链表冒泡排序。
原创
福大大架构师每日一题
修改于 2021-03-15 10:10:29
修改于 2021-03-15 10:10:29
2021-03-14：手写代码：单链表冒泡排序。
福大大 答案2021-03-14：
遍历链表，算出元素个数，假设为N。需要嵌套循环，外循环N-1轮，每轮循环相邻交换N-1次。
代码用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 = BubbleSort(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 BubbleSort(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
//链表节点的个数
count := 0
//对链表节点计数
temp := head.Next
for temp != nil {
count++
temp = temp.Next
}
//有换头的可能，所以新增一个虚拟头节点
preHead := &ListNode{Next: head}
//冒泡
var pre, cur *ListNode
for i := 0; i < count; i++ {
pre = preHead
cur = preHead.Next
for j := 0; j < count-i; j++ {
if cur.Val > cur.Next.Val {
//相邻交换
pre.Next, cur.Next, cur.Next.Next, cur = cur.Next, cur.Next.Next, cur, cur.Next
}
pre = pre.Next
cur = cur.Next
}
}
//虚拟头节点的Next指针就是需要返回的节点
return preHead.Next
}执行结果如下：
图片
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读