Go语言程序实现单链表归并排序功能

代码示例评论阅读8分3秒

下面是一个简单的Go语言程序,该程序实现了单链表的归并排序功能:

package main  
  
import (  
	"fmt"  
)  
  
// ListNode represents a node in the linked list  
type ListNode struct {  
	Val  int  
	Next *ListNode  
}  
  
// sortList sorts a linked list using merge sort algorithm.  
func sortList(head *ListNode) *ListNode {  
	if head == nil || head.Next == nil {  
		return head  
	}  
  
	// Split the list into two halves  
	mid := getMiddle(head)  
	nextToMid := mid.Next  
	mid.Next = nil  
  
	// Sort the two halves  
	left := sortList(head)  
	right := sortList(nextToMid)  
  
	// Merge the sorted halves  
	sortedList := merge(left, right)  
	return sortedList  
}  
  
// merge merges two sorted linked lists into one.  
func merge(l1 *ListNode, l2 *ListNode) *ListNode {  
	dummy := &ListNode{}  
	current := dummy  
  
	for l1 != nil && l2 != nil {  
		if l1.Val < l2.Val {  
			current.Next = l1  
			l1 = l1.Next  
		} else {  
			current.Next = l2  
			l2 = l2.Next  
		}  
		current = current.Next  
	}  
  
	if l1 != nil {  
		current.Next = l1  
	}  
  
	if l2 != nil {  
		current.Next = l2  
	}  
  
	return dummy.Next  
}  
  
// getMiddle finds and returns the middle node of a linked list.  
func getMiddle(head *ListNode) *ListNode {  
	if head == nil {  
		return head  
	}  
  
	slow := head  
	fast := head  
  
	for fast.Next != nil && fast.Next.Next != nil {  
		slow = slow.Next  
		fast = fast.Next.Next  
	}  
  
	return slow  
}  
  
// printList prints the elements of a linked list.  
func printList(head *ListNode) {  
	for head != nil {  
		fmt.Printf("%d ", head.Val)  
		head = head.Next  
	}  
	fmt.Println()  
}  
  
func main() {  
	// Create a sample linked list: 4 -> 2 -> 1 -> 3  
	head := &ListNode{Val: 4}  
	head.Next = &ListNode{Val: 2}  
	head.Next.Next = &ListNode{Val: 1}  
	head.Next.Next.Next = &ListNode{Val: 3}  
  
	// Print the original list  
	fmt.Println("Original List:")  
	printList(head)  
  
	// Sort the list  
	sortedHead := sortList(head)  
  
	// Print the sorted list  
	fmt.Println("Sorted List:")  
	printList(sortedHead)  
}

这段代码实现的是对单链表的归并排序。文章源自Golang编程指南-https://www.va26.com/work/317.html

程序中的函数分别完成了以下功能:文章源自Golang编程指南-https://www.va26.com/work/317.html

sortList 函数:文章源自Golang编程指南-https://www.va26.com/work/317.html

这个函数是归并排序的主要逻辑。它首先检查链表是否为空或只有一个节点,如果是,则直接返回该节点(因为空链表或只有一个节点的链表已经是排序好的)。文章源自Golang编程指南-https://www.va26.com/work/317.html

如果链表有多个节点,函数会找到链表的中点,并将链表从中点分成两部分。文章源自Golang编程指南-https://www.va26.com/work/317.html

然后,递归地对每一半进行排序。文章源自Golang编程指南-https://www.va26.com/work/317.html

最后,使用 merge 函数将两个已排序的子链表合并成一个有序链表,并返回合并后的链表头节点。文章源自Golang编程指南-https://www.va26.com/work/317.html

merge 函数:文章源自Golang编程指南-https://www.va26.com/work/317.html

这个函数负责合并两个已经排序好的链表。文章源自Golang编程指南-https://www.va26.com/work/317.html

它创建一个哑节点(dummy node)作为合并后链表的起始点,并设置一个当前节点指针来追踪合并过程中的位置。文章源自Golang编程指南-https://www.va26.com/work/317.html

然后,函数比较两个输入链表当前节点的值,将较小值的节点添加到合并链表的末尾,并移动相应链表的当前节点指针。

这个过程会一直持续到两个输入链表中的一个被完全遍历。之后,函数会将另一个链表中剩余的部分直接连接到合并链表的末尾。

最后,函数返回合并后链表的头节点(哑节点的下一个节点)。

getMiddle 函数:

这个函数使用快慢指针技巧来找到链表的中点。

快指针每次移动两个节点,而慢指针每次移动一个节点。

当快指针到达链表末尾时,慢指针恰好位于链表的中点。

这个中点用于将链表分成大致相等的两部分,以便在 sortList 函数中进行递归排序。

printList 函数:

这是一个辅助函数,用于打印链表的所有节点值,以便验证排序结果。

main 函数:

在这个函数中,创建了一个示例链表,并调用 sortList 函数对其进行排序。

排序完成后,使用 printList 函数打印排序后的链表,以验证排序算法的正确性。

在上面的程序中,我们首先定义了ListNode结构来表示链表节点。sortList函数实现了归并排序算法,首先递归地将链表分成两半,直到链表为空或只有一个节点,然后合并已排序的两半。merge函数负责合并两个已排序的链表。getMiddle函数使用快慢指针技术来找到链表的中间节点。printList函数用于打印链表。

在main函数中,我们创建了一个示例链表,并对其进行了排序,然后打印出排序后的链表。

由于Go语言的特性,在实际应用中,通常会对错误进行更全面的处理,并可能将部分功能拆分成单独的包或模块以提高代码的可重用性和可测试性。

 
  • 本文由golang编程指南作者原创,请勿恶意转载!
  • 转载请务必保留本文链接:https://www.va26.com/work/317.html
匿名

发表评论

匿名网友
:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:
确定

拖动滑块以完成验证