题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解法1 歪门邪道
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ import java.util.List; import java.util.ArrayList; import java.util.Collections; public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { List<Integer> list = new ArrayList<>(); while (list1!=null){ list.add(list1.val); list1=list1.next; } while (list2!=null){ list.add(list2.val); list2=list2.next; } //排序 １ < ２ < ３ < ４ 递增的顺序 Collections.sort(list); ListNode head=null,//头 tail=null,//尾 newnode=null;//每次创建的新节点 for (int i = 0; i < list.size(); i++) { //创建新的节点 newnode=new ListNode(list.get(i)); //如果是第一个节点,就选创建出来头节点 if(i==0){ head =tail= newnode; }else{ //如果不是最后一个节点就往next添加节点 tail.next = newnode; tail=newnode; } } return head; } }
解法2 非递归
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { //合并前先判断一下两个链表是否为空，如果单个为空就直接返回 if(list1==null) return list2; if(list2==null) return list1; /* 合并中，无非就是比较各自首节点谁小，就把该节点从原链表中删除，在尾插到新节点处。 比较中，两个链表任何一个都不能为空。 */ ListNode head = null; ListNode end = null; //只有两个都不为空的时候，才同时进行比较 while(list1!=null && list2!=null){ //比较，找到节点小的一个 ListNode p = list1.val < list2.val ? list1 : list2; //如果这个小的节点是list1，那么list1就往后走一个 if( list1 == p){ list1 = list1.next; }else{ //否则list2就往后走 list2 = list2.next; } //判断是否是第一次，如果是第一次合并的话，就不能往.next处放，直接赋值就可 if(head == null){ head = p; end = p; }else{ end.next=p; end=p; } } /* 合并之后，可能会存在这么三种情况： 1、list1为空，但是list2不为空； 2、list1不为空，但是list2为空； 3、list1和list2都为空。 需要针对这三种情况做处理 */ if(list1 == null){ end.next = list2; } if(list2==null){ end.next = list1; } return head; } }
解法3 递归法
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if(list1==null) return list2; if(list2==null) return list1; //合并中，找到第一个小的节点 ListNode newNode = null; if(list1.val < list2.val){ newNode = list1; list1 = list1.next; }else{ newNode = list2; list2 = list2.next; } //合并剩下的节点 newNode.next = Merge(list1,list2); return newNode; } }
