首页 > 试题广场 >

合并两个排序的链表

[编程题]合并两个排序的链表
  • 热度指数：1194357 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： ，
要求：空间复杂度 ，时间复杂度

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：


或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

示例1

输入

{1,3,5},{2,4,6}

输出

{1,2,3,4,5,6}
示例2

输入

{},{}

输出

{}
示例3

输入

{-1,2,4},{1,3,4}

输出

{-1,1,2,3,4,4}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
Go
时间漫过记忆海头像 时间漫过记忆海 
package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
*/
func Merge( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
    // write code here
    p1, p2 := pHead1, pHead2
    head := &ListNode{}
    p := head
    for p1 != nil && p2 != nil {
        if p1.Val < p2.Val {
            p.Next = p1
            p1 = p1.Next
        } else {
            p.Next = p2
            p2 = p2.Next
        }
        p = p.Next
    }
    if p1 != nil {
        p.Next = p1
    } else if p2 != nil{
        p.Next = p2
    }
    return head.Next
}

发表于 2023-04-14 19:47:34 回复(0)
Go
可可西里的苍穹头像 可可西里的苍穹 
func Merge( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
    // write code here
   
    if pHead1 == nil {
        return pHead2
    }
    
    if pHead2 == nil {
        return pHead1
    }
    
    head := &ListNode{Val:-1}
    cur := head
    
    for pHead1 != nil && pHead2 != nil {
        if pHead1.Val <= pHead2.Val{
            cur.Next = pHead1
            pHead1 = pHead1.Next
        }else {
            cur.Next = pHead2
            pHead2 = pHead2.Next
        }
        cur = cur.Next
 
    }
    
           
        if pHead1 != nil {
            cur.Next = pHead1
        }
        
        if pHead2 != nil {
            cur.Next = pHead2
        }
    
    return head.Next
}

发表于 2022-09-07 21:51:27 回复(0)
Go
风轻云淡.头像 风轻云淡. 
func Merge( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
    // write code here
    head:=new(ListNode)
    tmp:=head
    for pHead1!=nil && pHead2!=nil{
        if pHead1.Val<=pHead2.Val{
            tmp.Next=pHead1
            pHead1=pHead1.Next
        }else{
            tmp.Next=pHead2
            pHead2=pHead2.Next
        }
        tmp=tmp.Next
    }
    if pHead1!=nil{
        tmp.Next=pHead1
    }
    if pHead2!=nil{
        tmp.Next=pHead2
    }
    return head.Next
}

发表于 2022-04-17 10:12:34 回复(0)
Go
admxt头像 admxt
func Merge( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
    // write code here
    if pHead1==nil{
        return pHead2
    }
    if pHead2==nil{
        return pHead1
    }
    head:=pHead1
    second:=pHead2
    if pHead1.Val>pHead2.Val{
        head=pHead2
        second=pHead1
    }
    first:=head.Next
    pre:=head
    for{
        if first==nil{
            pre.Next=second
            break
        }
        if second==nil{
            pre.Next=first
            break
        }
        if first.Val<second.Val{
           pre.Next=first
           pre=first
           first=first.Next
        } else{
           pre.Next=second
           pre=second
           second=second.Next
        }
    }
    return head
}
发表于 2022-02-24 14:21:52 回复(1)
Go
恒衡头像 恒衡
Go 解题方法 
func Merge( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
/*思路：
新建一个头节点，然后从两个链表中取出较小值，放置于头节点链表后
*/
    
    var ret = &ListNode{}
    head := ret
    for pHead1!=nil && pHead2!=nil{
        //取出较小的节点
        if pHead1.Val < pHead2.Val{
            ret.Next = pHead1
            pHead1 = pHead1.Next
        }else{
            ret.Next = pHead2
            pHead2 = pHead2.Next
        }
        ret = ret.Next
    }
    //如果某一链表还有数据，则直接添加到ret链表后面
    if pHead1!=nil{
        ret.Next = pHead1
    }
	if pHead2!=nil{
        ret.Next = pHead2
    }
    
    // 头节点无数据，需略过
    return head.Next
}


发表于 2022-01-01 16:34:51 回复(0)
Go
王飞-6头像 王飞-6
迭代版本 
func Merge( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
    du := new(ListNode)
    t := du
    for pHead1 != nil && pHead2 != nil {
        if pHead1.Val < pHead2.Val {
            t.Next = pHead1
            pHead1 = pHead1.Next
            t = t.Next
        } else {
            t.Next = pHead2
            pHead2 = pHead2.Next
            t = t.Next
        }
    }
    if pHead1 != nil {
        t.Next = pHead1
    }
    if pHead2 != nil {
        t.Next = pHead2
    }
    return du.Next
}



发表于 2021-11-26 15:33:42 回复(0)
Go
rouroumaibing头像 rouroumaibing 
package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
*/
func Merge( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
    // write code here
    if pHead1 == nil {
        return pHead2
    }
    if pHead2 == nil{
        return pHead1
    }
    if pHead1.Val <= pHead2.Val{
        pHead1.Next = Merge(pHead1.Next, pHead2)
        return pHead1
    }else{
        pHead2.Next = Merge(pHead2.Next, pHead1)
        return pHead2
    }
}

发表于 2021-10-31 18:02:03 回复(0)
Go
重庆扛把子头像 重庆扛把子
func Merge(pHead1 *ListNode, pHead2 *ListNode) *ListNode {
    // write code here
    head := &ListNode{}
    cur := head
    for pHead1 != nil && pHead2 != nil {
        if pHead1.Val <= pHead2.Val {
            cur.Next = pHead1
            pHead1 = pHead1.Next
        } else {
            cur.Next = pHead2
            pHead2 = pHead2.Next
        }
        cur = cur.Next
    }

    switch {
    case pHead1 != nil:
        cur.Next = pHead1
    case pHead2 != nil:
        cur.Next = pHead2
    }
    return head.Next
}
发表于 2021-09-12 15:50:04 回复(0)
Go
永不panic头像 永不panic 
指针一定不能整个将指向的内容变换，要赋值指针内部里面的，比如next，否则res和遍历的node不匹配

func MergeSe(pHead1 *ListNode, pHead2 *ListNode) *ListNode {
	if pHead1 == nil && pHead2 == nil {
		return nil
	}
	node := new(ListNode)
	res := node
	for pHead1 != nil || pHead2 != nil {
		if pHead1 == nil {
			(*node).Next = pHead2
			break
		} else if pHead2 == nil {
			(*node).Next = pHead1
			break
		} else {
			if pHead1.Val > pHead2.Val {
				(*node).Next = pHead2
				pHead2 = pHead2.Next
			} else {
				(*node).Next = pHead1
				pHead1 = pHead1.Next
			}
			node = (*node).Next
		}
	}
	return res.Next
}

发表于 2021-09-09 10:10:29 回复(0)
Go
梵音2021头像 梵音2021
func Merge( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
    // write code here
    head := &ListNode{}
    result := head
    
    for pHead1 != nil && pHead2 != nil {
        if pHead1.Val < pHead2.Val {
            head.Next = pHead1
            pHead1 = pHead1.Next
        } else {
            head.Next = pHead2
            pHead2 = pHead2.Next
        }
        head = head.Next
    }
    
    if pHead1 != nil {
        head.Next = pHead1
    }
    if pHead2 != nil {
        head.Next = pHead2
    }
    return result.Next
}
发表于 2021-08-18 23:16:08 回复(0)
提交观点

问题信息

链表 2021
来自：2021届阅文测试开发...
难度：
10条回答 172096浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号