链表-合并两个有序链表,O(1)空间复杂度可否?

问题

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

示例

输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4

解法一

看到这个题目,最直观的是什么?排序嘛,对不,我们将链表转化为数组,直接排序,最后组装一个新的链表,完事,因为两个链表本身 就是有序的,所以转化后的数组就是有序的,我们只需要依次比较两个数组,如下图:

type ListNode struct {
     Val int
     Next *ListNode
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    //声明三个切片
    slice1 := make([]int,0)
    slice2 := make([]int,0)
    slice3 := make([]int,0)
    //将链表转换为数组
    for l1 != nil{
        slice1 = append(slice1,l1.Val)
        l1 = l1.Next
    }
    for l2 != nil{
        slice2 = append(slice2,l2.Val)
        l2 = l2.Next
    }
    //开始依次比较,这里一定注意切片越界
    i,j := 0,0
    for i<len(slice1) && j <len(slice2){
        if slice1[i] <= slice2[j] {
            slice3 = append(slice3,slice1[i])
            i++
        }else{
            slice3 =append(slice3,slice2[j])
            j++
        }
    }
    //将切片剩余的值补充上去后面
    for i<len(slice1){
        slice3 = append(slice3,slice1[i])
        i++
    }
    for j<len(slice2){
        slice3 = append(slice3,slice2[j])
        j++
    }
    //将最终排好序的数组转换为链表进行返回
    var head,result  *ListNode = nil,nil
    for _,v := range slice3{
        if head  == nil{
            head = &ListNode{v,nil}
            result = head
            continue
        }
        head.Next = &ListNode{v,nil}
        head = head.Next
    }
    return result
}

上面代码我们可以看出申请了三个切片空间,其空间复杂度为O(n),在链表长度比较大的情况下,占用的额外空间回比较大,那怎么优化呢?

解法二

上面的解法一,我们申请了存放链表元素的数组空间,空间复杂度是O(n),那么不转数组行不?O(1)的空间复杂度可以完成吗,能不转数组吗?直接根据链表来比较,这样就不要用消耗内存空间了,我们一起尝试一下?如下图

type ListNode struct {
     Val int
     Next *ListNode
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    //如果l1是nil,直接返回l2,因为链表本身是有序的
    if l1 == nil{
        return l2
    }
    //如果l2是nil,直接返回l2,因为链表本身是有序的
    if l2  == nil{
        return l1
    }
   //声明两个指针变量
    temp := &ListNode{-1,nil}
    result := temp
    for l1 != nil && l2 != nil{
        if l1.Val < l2.Val{ // l1链接
            n1 := l1
            temp.Next = n1
            temp = temp.Next
            l1 = l1.Next
        }else{ // l2链接
            n2 := l2
            temp.Next = n2
            temp = temp.Next
            l2 = l2.Next
        } 
    }
     //补全剩余的链表
    if l1 == nil {
        temp.Next = l2
    }
    if l2 == nil {
        temp.Next = l1
    }
    return result.Next
}

解法三

递归法,代码简单,感兴趣的了解一下,理解为最终要合并的两个链表长度一个为1,一个为0,满足递归终止条件。

type ListNode struct {
     Val int
     Next *ListNode
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    //如果l1是nil,直接返回l2,因为链表本身是有序的
    if l1 == nil{
        return l2
    }
    //如果l2是nil,直接返回l2,因为链表本身是有序的
    if l2  == nil{
        return l1
    }
   if l1.Val < l2.Val{
        //将l1的next节点指向为l2,也就是将大的挂在小的后面
        l1.Next = mergeTwoLists(l1.Next,l2)
        return l1
    }else{
        //将l2的next节点指向为l1,也就是将大的挂在小的后面
        l2.Next = mergeTwoLists(l2.Next,l1)
        return l2
    } 
}

本文分享自微信公众号 - GoLang那点事(aweiaichitudou)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券