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 }
执行结果如下: