题目描述
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
例如:
输入:链表一:1->3->5->7 链表二:2->4->6->8
输出:链表三:1->2->3->4->5->6->7->8
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function Merge(pHead1, pHead2)
{
//方法一:递归调用
/*
var res;
if(pHead1==null) return pHead2;//直至链表pHead1为空返回剩余的链表pHead2,进行拼接
if(pHead2==null) return pHead1;//直至链表pHead2为空返回剩余的链表pHead1,进行拼接
if(pHead1.val>pHead2.val){
res=pHead2;
res.next=Merge(pHead1,pHead2.next);//递归调用Merge方法
}else{
res=pHead1;
res.next=Merge(pHead1.next,pHead2);//递归调用Merge方法
}
return res;
*/
//方法二:while循环
var pHead3 = new ListNode(-1);//实例化一个链表,里面的值是-1;因程序需要创建的节点
var l3 = pHead3;//l3链表节点用于移动,拼接链表元素
while(pHead1 !== null && pHead2 !== null) {
if(pHead1.val <= pHead2.val) {
l3.next = pHead1;
pHead1 = pHead1.next;
} else {
l3.next = pHead2;
pHead2 = pHead2.next;
}
l3 = l3.next;
}
l3.next = (pHead1===null) ?pHead2:pHead1;//循环完某一链表后,将另一链表剩下的部分直接加入到l3
return pHead3.next;//输出节点-1之后的链表,即我们需要的合成后的单调不减链表
}
前端面试的时候,面试官最喜欢问的链表题目之一,一定要好好理解。