Go 编程实例【合并两个有序链表】

合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成。

/root/www/test/test.go

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	// 如果 l1 为空，则直接返回 l2
	if l1 == nil {
		return l2
	}
	// 如果 l2 为空，则直接返回 l1
	if l2 == nil {
		return l1
	}

	// 定义一个 dummy 节点作为合并后的链表的头节点
	dummy := &ListNode{}
	// 定义一个 cur 指针指向 dummy 节点，用于遍历合并后的链表
	cur := dummy

	// 遍历 l1 和 l2，将较小的节点逐个加入到合并后的链表中
	for l1 != nil && l2 != nil {
		if l1.Val > l2.Val {
			cur.Next = l2
			l2 = l2.Next
		} else {
			cur.Next = l1
			l1 = l1.Next
		}
		// 移动 cur 指针到下一个节点
		cur = cur.Next
	}

	// 如果 l1 还有剩余节点，将剩余节点全部加入到合并后的链表中
	if l1 != nil {
		cur.Next = l1
	} else if l2 != nil { // 如果 l2 还有剩余节点，将剩余节点全部加入到合并后的链表中
		cur.Next = l2
	}

	// 返回合并后的链表的头节点
	return dummy.Next
}

func main() {
	// 创建两个有序链表
	l1 := &ListNode{1, &ListNode{2, &ListNode{4, nil}}}
	l2 := &ListNode{1, &ListNode{3, &ListNode{4, nil}}}

	// 合并两个有序链表
	merged := mergeTwoLists(l1, l2)

	// 遍历合并后的链表，并打印每个节点的值
	for cur := merged; cur != nil; cur = cur.Next {
		fmt.Println(cur.Val)
	}
}

root@debiancc:~/www/test# go run test.go 
1
1
2
3
4
4
root@debiancc:~/www/test# 

说明

在这段代码中，我们定义了一个链表节点类型 ListNode，并实现了一个合并两个有序链表的函数 mergeTwoLists。这个函数的核心思路是利用一个 dummy 节点作为合并后的链表的头节点，然后通过遍历两个有序链表，逐个将较小的节点加入到合并后的链表中。

具体来说，我们先判断 l1 和 l2 中哪个节点的值更小，然后将这个节点加入到合并后的链表中。随后，我们将指向这个节点的指针向后移动，继续比较下一个节点。不断重复这个过程，直到其中一个链表遍历完毕。

最后，如果 l1 还有剩余节点，我们将剩余。