30.合并两个有序的链表

71 阅读 0 评论 47 点赞

我是靠谱客的博主勤奋薯片，最近开发中收集的这篇文章主要介绍30.合并两个有序的链表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解析：
递归
①比较两个有序链表p1和p2的当前结点值，如果p1的结点值大于p2的结点值，将当前p2的结点指向当前p1结点，否则当前p1结点指向当前p2结点；
②接下来在比较p1结点的下一结点和p2结点或比较p2结点的下一结点和p1结点；
③重复①②直到递归条件结束。

 public ListNode Merge1(ListNode list1,ListNode list2) {
        //递归结束条件
   if (list1==null)  return list2;
   if (list2==null)  return list1;
   if (list1==null&&list2==null)  return null;
   if (list1.val > list2.val){
     list2.next = Merge1(list1, list2.next);
     return list2;
   }else{
    list1.next = Merge1(list1.next, list2);
    return  list1;
   }
  }