LeetCode-21.合并两个有序链表

链表#

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

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

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

自己的解法

手撕

1
/**
2
 * Definition for singly-linked list.
3
 * type ListNode struct {
4
 *     Val int
5
 *     Next *ListNode
6
 * }
7
 */
8
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
9
    dummy := &ListNode{}
10
    cur := dummy
11
    if list1 == nil {
12
        return list2
13
    }
14

15
    if list2 == nil {
16
        return list1
17
    }
18

19
    for list1 != nil || list2 != nil {
20
        if list1 == nil {
21
            cur.Next = list2
22
            return dummy.Next
23
        }
24

25
        if list2 == nil {
26
            cur.Next = list1
27
            return dummy.Next
28
        }
29

30
        if list1.Val < list2.Val {
31
            cur.Next = list1
32
            cur = cur.Next
33
            list1 = list1.Next
34
        }else {
35
            cur.Next = list2
36
            cur = cur.Next
37
            list2 = list2.Next
38
        }
39
    }
40
    return dummy.Next
41
}

ai润色后

1
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
2
    dummy := &ListNode{}
3
    cur := dummy
4

5
    for list1 != nil && list2 != nil {
6
        if list1.Val < list2.Val {
7
            cur.Next = list1
8
            list1 = list1.Next
9
        } else {
10
            cur.Next = list2
11
            list2 = list2.Next
12
        }
13
        cur = cur.Next
14
    }
15

16
    if list1 != nil {
17
        cur.Next = list1
18
    } else {
19
        cur.Next = list2
20
    }
21

22
    return dummy.Next
23
}

递归

1
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
2
    if list1 == nil {
3
        return list2
4
    }
5
    if list2 == nil {
6
        return list1
7
    }
8

9
    if list1.Val < list2.Val {
10
        list1.Next = mergeTwoLists(list1.Next, list2)
11
        return list1
12
    } else {
13
        list2.Next = mergeTwoLists(list1, list2.Next)
14
        return list2
15
    }
16
}