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

悠悠 2023-10-09 21:13 14阅读 0赞

#### 阅读目录 ####

*  合并两个有序链表
 *   *  说明

## 合并两个有序链表 ##

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

![在这里插入图片描述][e373752455394fd982f42224b82ae3ef.png]

`/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 还有剩余节点，我们将剩余。

[e373752455394fd982f42224b82ae3ef.png]: https://img-blog.csdnimg.cn/e373752455394fd982f42224b82ae3ef.png