合并两个排序的链表【Java版】
合并两个排序的链表
http://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337
1)朴素方法
public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { //没有虚拟头结点的坏处:要额外拎出来头部的过程,而不是统一 if(list1 == null)return list2; if(list2 == null)return list1; ListNode p0 = null;//标记头部,不能动 if(list1.val < list2.val){ p0=list1; list1=list1.next; } else{ p0=list2; list2=list2.next; } ListNode p=p0; while(list1 != null && list2 != null){//正式主体过程 if(list1.val < list2.val){ p.next=list1; p=p.next;//【千万别漏了这个】 list1=list1.next; } else{ p.next=list2; p=p.next; list2=list2.next;//直接修改题目变量,可节约空间 } } if(list1==null)p.next=list2; if(list2==null)p.next=list1; return p0; } } // 时间 O(N), 空间 O(1)
2)虚拟头结点:统一过程&精简代码
public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { //建立虚拟头结点,可以统一过程&精简代码,同时减少或不用考虑头部的情况 //此代码和上面相比,只有函数里的第一行和最后一行是修改的 ListNode vHead = new ListNode(Integer.MIN_VALUE);//建立虚拟头结点 //建立的时候不能用null,必须实例化 ListNode p=vHead; while(list1 != null && list2 != null){ if(list1.val < list2.val){ p.next=list1; p=p.next; list1=list1.next; } else{ p.next=list2; p=p.next; list2=list2.next; } } if(list1==null)p.next=list2; if(list2==null)p.next=list1; return vHead.next;//虚拟头结点一直在那不动,返回它的下一个即为第一个真实节点 } }
《剑指Offer-Java题解》 文章被收录于专栏
《剑指Offer-Java题解》