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. 排序链表
评论