【剑指Offer】16、合并两个排序的链表

  题目描述:

  输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

  解题思路:

  首先需要判断几个特殊情况,即判断输入的两个指针是否为空。如果第一个链表为空,则直接返回第二个链表;如果第二个链表为空,则直接返回第一个链表。如果两个链表都是空链表,合并的结果是得到一个空链表。

  两个链表都是排序好的,我们只需要从头遍历链表,判断当前指针,哪个链表中的值小,即赋给合并链表指针,剩余的结点仍然是排序的,所以合并的步骤和之前是一样的,所以这是典型的递归过程,用递归可以轻松实现。

  举例:

![](https://img2018.cnblogs.com/blog/1608161/201904/1608161-20190427150721322-366814884.png)

  编程实现(Java):

	//方法一:递归实现
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1==null)
return list2;
if(list2==null)
return list1;
ListNode head=null; //头节点
if(list1.val<=list2.val){
head=list1;
head.next=Merge(list1.next,list2);
}else{
head=list2;
head.next=Merge(list1,list2.next);
}
return head;
} //方法二:非递归实现
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1==null)
return list2;
if(list2==null)
return list1;
ListNode head=new ListNode(-1);//头节点
ListNode thehead=head;
while(list1!=null && list2!=null){
if(list1.val<=list2.val){
thehead.next=list1;
list1=list1.next;
}else{
thehead.next=list2;
list2=list2.next;
}
thehead=thehead.next;
}
if(list1!=null) //归并完需要检查哪个链表还有剩余
thehead.next=list1;
if(list2!=null)
thehead.next=list2;
return head.next;
}
上一篇:jQuery插件综合应用(二)文字为主的页面


下一篇:DNS Tunnel隧道隐蔽通信实验 && 尝试复现特征向量化思维方式检测