链表合并之二

  1 package LinkTogether;
  2 
  3 import java.util.ArrayList;
  4 import java.util.LinkedList;
  5 
  6 /*
  7  * 两个升序链表合并，不减顺序输出，使用队列
  8  * */
  9 
 10 class ListNode {
 11     int val;
 12     ListNode next = null;
 13 
 14     ListNode(int val) {
 15         this.val = val;
 16     }
 17 }
 18 
 19 public class Demo05 {
 20     public static void main(String[] args) {
 21         ListNode n1 = new ListNode(2);
 22         ListNode n2 = new ListNode(5);
 23         ListNode n3 = new ListNode(7);
 24         ListNode n4 = new ListNode(8);
 25         n1.next = n2;
 26         n2.next = n3;
 27         n3.next = n4;
 28         
 29         ListNode n5 = new ListNode(1);
 30         ListNode n6 = new ListNode(6);
 31         ListNode n7 = new ListNode(10);
 32         ListNode n8 = new ListNode(80);
 33         n5.next = n6;
 34         n6.next = n7;
 35         n7.next = n8;
 36         
 37         n1 = Merge(n1,n5);
 38         
 39         print(n1);
 40     }
 41     public static ListNode Merge(ListNode list1,ListNode list2) {
 42         if(list1 == null && list2 == null)return null;
 43         if(list1 == null)return list2;
 44         if(list2 == null)return list1;
 45         /*
 46          * 将两个链表分别放在link1和link1中，便于使用相关方法
 47          * */
 48         LinkedList<Integer> link1 = new LinkedList<Integer>();
 49         ListNode temp1 = list1;
 50         while(temp1 != null){
 51             link1.add(temp1.val);
 52             temp1 = temp1.next;
 53         }
 54         LinkedList<Integer> link2 = new LinkedList<Integer>();
 55         ListNode temp2 = list2;
 56         while(temp2 != null){
 57             link2.add(temp2.val);
 58             temp2 =temp2.next;
 59         }
 60         /*
 61          * 将link1和link2中的内容按照不递减的顺序放入arr中
 62          * */
 63         ArrayList<Integer> arr = new ArrayList<>();
 64         while((! link1.isEmpty()) && (! link2.isEmpty())){
 65             if(link1.element() <= link2.element()){
 66                 arr.add(link1.poll());
 67             }
 68             if((link1.isEmpty()) || (link2.isEmpty()))break;
 69             if(link1.element() > link2.element()){
 70                 arr.add(link2.poll());
 71             }
 72         }
 73         while(! link1.isEmpty()){
 74             arr.add(link1.poll());
 75         }
 76         while(! link2.isEmpty()){
 77             arr.add(link2.poll());
 78         }
 79         /*
 80          * 将题目中的两个链表相连接，
 81          * */    
 82         int flag = 0;
 83         ListNode temp = list1;
 84         while(true){
 85             if(temp.next == null){
 86                 flag ++;
 87                 if(flag == 2)break;
 88                 temp.next = list2;
 89             }
 90             temp = temp.next;
 91         }
 92         /*
 93          * 将arr中的数据取出，放入合并后的链表中
 94          * */
 95         list1.val = arr.get(0);
 96         temp = list1.next;
 97         for(int i=1;i<arr.size();i++){
 98             temp.val = arr.get(i);
 99             temp = temp.next;
100         }
101         return list1;
102     }
103 
104     private static void print(ListNode n) {
105         System.out.println(n.val);
106         if(n.next != null){
107             print(n.next);
108         }
109     }
110 }