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

  • 代码如下
  1 public class Demo4 {
  2 
  3     public static void main(String[] args) {
  4         // 先创建多个节点,供测试使用
  5         ListNode listNode1 = new ListNode(1);
  6         ListNode listNode2 = new ListNode(2);
  7         ListNode listNode3 = new ListNode(6);
  8         ListNode listNode4 = new ListNode(14);
  9         ListNode listNode5 = new ListNode(15);
 10         // 把各个节点链起来
 11         listNode1.next = listNode2;
 12         listNode2.next = listNode3;
 13         listNode3.next = listNode4;
 14         listNode4.next = listNode5;
 15         listNode5.next = null;
 16         
 17         ListNode listNode6 = new ListNode(6);
 18         ListNode listNode7 = new ListNode(7);
 19         ListNode listNode8 = new ListNode(10);
 20         ListNode listNode9 = new ListNode(11);
 21         ListNode listNode10 = new ListNode(13);
 22         listNode6.next = listNode7;
 23         listNode7.next = listNode8;
 24         listNode8.next = listNode9;
 25         listNode9.next = listNode10;
 26         listNode10.next = null;
 27 
 28         System.out.println("原始链表1中的数据如下:");
 29         printList(listNode1);
 30         System.out.println("\n原始链表2中的数据如下:");
 31         printList(listNode6);
 32         
 33         System.out.println("\n\n合并之后的链表数据如下:");
 34         ListNode mergeHead = Merge(listNode1, listNode6);
 35         printList(mergeHead);
 36     }
 37     
 38     /**
 39      * 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
 40      */
 41     public static ListNode Merge(ListNode list1,ListNode list2) {
 42         if(list1 == null) return list2;
 43         if(list2 == null) return list1;
 44         
 45         ListNode res = null;
 46         if(list1.val < list2.val){
 47             res = list1;
 48             res.next = Merge(list1.next, list2);
 49         }else{
 50             res = list2;
 51             res.next = Merge(list1, list2.next);
 52         }
 53         return res;
 54     }
 55     
 56     /**
 57      * 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
 58      */
 59     public static ListNode myMerge(ListNode list1,ListNode list2) {
 60         if(list1 == null) return list2;
 61         if(list2 == null) return list1;
 62         ListNode mergeHead = null;
 63         ListNode current = null;
 64         while(list1 != null && list2 != null){
 65             if(list1.val <= list2.val){
 66                 if(mergeHead == null){
 67                     mergeHead = current = list1;
 68                 }else{
 69                     current.next = list1;
 70                     current = current.next;
 71                 }
 72                 list1 = list1.next;
 73             }else{
 74                 if(mergeHead == null){
 75                     mergeHead = current = list2;
 76                 }else{
 77                     current.next = list2;
 78                     current = current.next;
 79                 }
 80                 list2 = list2.next;
 81             }
 82         }
 83         if(list1 == null){
 84             current.next = list2;
 85         }else{
 86             current.next = list1;
 87         }
 88         return mergeHead;
 89     }
 90 
 91     /**
 92      * 遍历单链表
 93      * @param listNode
 94      */
 95     public static void printList(ListNode listNode) {
 96         ListNode tempNode = listNode;
 97         while(tempNode != null){
 98             System.out.printf("%d\t",tempNode.val);
 99             tempNode = tempNode.next;
100         }
101     }
102 }
1 public class ListNode {
2     int val;
3     ListNode next = null;
4 
5     public ListNode(int val) {
6         this.val = val;
7     }
8 }
  • 运行结果

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

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

 

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄