0021.merge-two-sorted-lists.md

0021.Merge-Two-Sorted-Lists

Description

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Tags: Linked List

题解

思路1

题意是用一个新链表来合并两个已排序的链表，那我们只需要从头开始比较已排序的两个链表，新链表指针每次指向值小的节点，依次比较下去，最后，当其中一个链表到达了末尾，我们只需要把新链表指针指向另一个没有到末尾的链表此时的指针即可。

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    head := &ListNode{}
    tmp := head

    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            tmp.Next = l1
            l1 = l1.Next
        } else {
            tmp.Next = l2
            l2 = l2.Next
        }
        tmp = tmp.Next
    }
    if l1 != nil {
        tmp.Next = l1
    } else {
        tmp.Next = l2
    }

    return head.Next
}

思路2

结语

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：awesome-golang-algorithm