首页 > 其他 > 详细

剑指offer16

时间:2018-01-17 13:37:02      阅读:222      评论:0      收藏:0      [点我收藏+]
package jianzhiOffer; /**  * 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需  * 要合成后的链表满足单调不减规则。  * @author user  *   */ public class ch16 { /*  * 思路一:采用递归的方式,很简单,先合并头结点,得出合并后  * 的头结点,再得到剩下的链表合并后的头结点,以此类推  */ public ListNode Merge(ListNode list1,ListNode list2) { ListNode head;         if(list1 == null) {          return list2;         }         if(list2 == null) {          return list1;         }      if(list1.val > list2.val) {      head = list2;      head.next = Merge(list1, list2.next);         } else {          head = list1;          head.next = Merge(list1.next, list2);         }      return head;     }
/*
	 * 此题意在考察代码的鲁棒性,若链表太长,就不能使用递归的方式了,
	 * 因此面试中应直接排除掉用递归
	 * 思路二:非递归,创建一个新节点,将两个链表各个节点进行比较,
	 * 按要求加入新节点
	 */
	public ListNode Merge2(ListNode list1,ListNode list2) {
		ListNode node = new ListNode(-1);
		ListNode megeNode = node;
		if(list1 == null) {
			return list2;
		}
		if(list2 == null) {
			return list1;
		}
		while(list1 != null && list2 != null) {
			if(list1.val < list2.val) {
				megeNode.next = list1;
				list1 = list1.next;
			} else {
				megeNode.next = list2;
				list2 = list2.next;
			}
			megeNode = megeNode.next;
		}
		if(list1 != null) {
			megeNode.next = list1;
		}
		if(list2 != null) {
			megeNode.next = list2;
		}
		return node.next;
	}
}


剑指offer16

原文:http://blog.51cto.com/12222886/2061983

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!