龙空技术网

2021-03-14:手写代码:单链表冒泡排序

福大大架构师每日一题 162

前言:

当前大家对“链表实现冒泡排序算法流程图”大致比较珍视,朋友们都需要知道一些“链表实现冒泡排序算法流程图”的相关资讯。那么小编同时在网上搜集了一些有关“链表实现冒泡排序算法流程图””的相关资讯,希望你们能喜欢,你们快快来了解一下吧!

2021-03-14:手写代码:单链表冒泡排序。

福大大 答案2021-03-14:

遍历链表,算出元素个数,假设为N。需要嵌套循环,外循环N-1轮,每轮循环相邻交换N-1次。

代码用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 = 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}

执行结果如下:

***

[力扣148. 排序链表]()

[评论]()

标签: #链表实现冒泡排序算法流程图