让我们一起啃算法----合并两个有序链表

合并两个有序链表(Merge-Two-Sorted-Lists)

题干如下:

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
示例:
  输入:1->2->4, 1->3->4
  输出:1->1->2->3->4->4
来源:力扣

这个题目和 两数相加 相似,都是考察对链表的操作。其实具体实现方式也差不多啦。

解题思路

根据题干我们知道,给定的两个链表是有序的。假设 l1 指向其中一个链表的头部,l2 指向另一个链表的头部,并初始化 head 和 current,使它们指向一个默认的节点。我们比较 l1 指向节点的值 V(l1) 与 l2 指向节点的值 V(l2) 的大小,如果 V(l1) 的值小于 V(l2) 的值,则使 current.next 指向 l1 这个节点,current 指向下一个节点,l1 指向 l1的下一个节点,反之,则使 current.next 指向 l2 这个节点,current 指向下一个节点, l2 指向 l2的下一个节点。

具体流程图如下:

注: l1 和 l2 存在有一个指向 空 时的处理方案是:将 current.next 指向不是空的的链表即可,因为给定的两个链表本身是有序的。

代码实现

GO语言实现

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    var (
        head = &ListNode{}
        current = head
    )

    for true {

        // l1 为空时,将 current.next 指向 l2 即可
        if l1 == nil {
            current.Next = l2
            break
        }

        // l2 为空时,将 current.next 指向 l1 即可
        if l2 == nil {
            current.Next = l1
            break
        }

        // 如果 l1的值 小于 l2的值 current.next指向l1,l1后移
        if l1.Val < l2.Val {
            current.Next = l1
            l1 = l1.Next
        } else {
            // 如果 l2的值 小于等于 l1的值 current.next指向l2,l2后移
            current.Next = l2
            l2 = l2.Next
        }

        // current 后移一位
        current = current.Next
    }
    
    // head 指向的是默认的节点,head.next 才是结果链表的头节点
    return head.Next

}

总结

每天进步一点点,加油!
算法教程项目,每天更新一题,点个 star 支持一下呀:
https://github.com/wx-satellite/learning-a...

评论

暂无评论