当前位置：首页 > java >正文

合并两个有序链表

java 2025/5/1 15:07:33

题目：21. 合并两个有序链表

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

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按非递减顺序排列

解题思路

见代码。

实现代码

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {head := &ListNode{} //头结点cursor := head      //指针for l1 != nil && l2 != nil {if l1.Val < l2.Val {cursor.Next = l1l1 = l1.Next} else {cursor.Next = l2l2 = l2.Next}cursor = cursor.Next}//任一条到达尾部，直接拼上另一条if l1 == nil {cursor.Next = l2} else {cursor.Next = l1}return head.Next
}

单元测试

package leetcodeimport ("testing""github.com/stretchr/testify/assert""github.com/superproj/go-leetcode/structure"
)func Test_mergeTwoLists(t *testing.T) {assert := assert.New(t)type args struct {first  []intsecond []int}tests := []struct {args argswant []int}{{args: args{[]int{}, []int{}},want: []int{},},{args: args{[]int{1}, []int{1}},want: []int{1, 1},},{args: args{[]int{1, 2, 3, 4}, []int{1, 2, 3, 4}},want: []int{1, 1, 2, 2, 3, 3, 4, 4},},{args: args{[]int{1, 2, 3, 4, 5}, []int{1, 2, 3, 4, 5}},want: []int{1, 1, 2, 2, 3, 3, 4, 4, 5, 5},},{args: args{[]int{1}, []int{9, 9, 9, 9, 9}},want: []int{1, 9, 9, 9, 9, 9},},{args: args{[]int{9, 9, 9, 9, 9}, []int{1}},want: []int{1, 9, 9, 9, 9, 9},},{args: args{[]int{2, 3, 4}, []int{4, 5, 6}},want: []int{2, 3, 4, 4, 5, 6},},{args: args{[]int{1, 3, 8}, []int{1, 7}},want: []int{1, 1, 3, 7, 8},},}for _, tt := range tests {first := structure.Ints2List(tt.args.first)second := structure.Ints2List(tt.args.second)actual := structure.List2Ints(mergeTwoLists(first, second))assert.Equal(tt.want, actual)}
}

知识星球：云原生AI实战营。10+ 高质量体系课（ Go、云原生、AI Infra）、15+ 实战项目，P8 技术专家助你提高技术天花板，建立职场竞争力；
公众号：令飞编程，分享 Go、云原生、AI Infra 相关技术。回复「资料」免费下载 Go、云原生、AI 等学习资料；
哔哩哔哩：令飞编程，分享技术、职场、面经等，并有免费直播课「云原生AI高新就业课」，大厂级项目实战到大厂面试通关；

查看全文

http://www.xdnf.cn/news/3018.html