【作业8】链表专题：用递归合并排序链表

共以下 17 个回答

• 幽小皮 永久会员 2024年4月13日 下午8:46

  打卡

  “`
  public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  if(list1 == null){
  return list2;
  }else if(list2 == null){
  return list1;
  }
  if(list1.val <= list2.val){ list1.next = mergeTwoLists(list1.next, list2); return list1; }else{ list2.next = mergeTwoLists(list1, list2.next); return list2; }

  }```java
  

  0 赞同 0 条回复

  登录以回复
• Mr.肖 永久会员 2024年3月27日 下午6:46

  class Solution {
      public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
          //递归解法
          if(list1 == null){
              return list2;
          }
          if(list2 == null){
              return list1;
          }
  
          if(list1.val <= list2.val){
              list1.next = mergeTwoLists(list1.next,list2);
              return list1;
          }else{
              list2.next = mergeTwoLists(list2.next,list1);
              return list2;
          }
  
  
  
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 泡芙 永久会员 2023年9月15日 下午2:06

  • Time：O(n+m)，n和m分别为链表l1, l2的长度,合并操作需遍历两链表。
  • Space：O(n+m)，递归调用栈

  lass Solution {
      // 合并后的链表
      public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
          // 结束条件
          if (list1 == null) {
              return list2;
          }
          if (list2 == null) {
              return list1;
          }
  
          // 关系式
          if (list1.val <= list2.val) {
              list1.next = mergeTwoLists(list1.next, list2);
              return list1;
          } else {
              list2.next = mergeTwoLists(list2.next, list1);
              return list2;
          }
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 八点上线 永久会员 2023年9月10日 下午7:07

  递归

  class Solution {
      public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
          if(list1 == null){
              return list2;
          }else if(list2 == null){
              return list1;
          }
          if(list1.val < list2.val){
              list1.next = mergeTwoLists(list1.next,list2);
              return list1;
          }
          list2.next = mergeTwoLists(list1,list2.next);
          return list2;
  
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• Thaddeus 永久会员 2023年9月3日 下午3:37

  打卡

  时间复杂度：O(m + n)

  空间复杂度：O(m + n)

  class Solution {
  public:
      ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
          if(list1 == nullptr) {
              return list2;
          }
          if(list2 == nullptr) {
              return list1;
          }
  
          if(list1->val <= list2->val) {
              list1->next = mergeTwoLists(list1->next, list2);
              return list1;
          }else {
              list2->next = mergeTwoLists(list1, list2->next);
              return list2;
          }
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• AD钙奶 普通 2023年9月1日 下午3:20

  递归

  class Solution {
      public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
          if(list1 == null) {
              return list2;
          }
          if(list2 == null) {
              return list1;
          }
          if(list1.val <= list2.val) {
              list1.next = mergeTwoLists(list1.next,list2);
              return list1;
          } else {
              list2.next = mergeTwoLists(list2.next,list1);
              return list2;
          }
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 纸飞机 永久会员 2023年8月10日 上午3:15

  class Solution {
  //递归
  public:
      ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
          if(!list1) return list2;
          if(!list2) return list1;
          ListNode*cur_1 = list1;
          ListNode*cur_2 = list2;
          ListNode* head ;
          if(cur_1->val<=cur_2->val)
          {
              head = cur_1;
              head->next = mergeTwoLists(cur_1->next,cur_2);
          }
          else
          {
              head = cur_2;
              head->next = mergeTwoLists(cur_1,cur_2->next);   
          }
          return head;
      }
  
  };
  

  0 赞同 0 条回复

  登录以回复
• 𬍤 永久会员 2023年7月28日 下午6:32

  class Solution {
      public ListNode mergeTwoLists(ListNode list1, ListNode list2) {        
          //递归
          if(list1 == null){
              return list2;
          }
          if(list2 == null){
              return list1;
          }
  
          if(list1.val <= list2.val){
              list1.next = mergeTwoLists(list1.next,list2);
              return list1;
          }else{
              list2.next = mergeTwoLists(list1,list2.next);
              return list2;
          }
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• LicodeCO.LTDao 普通 2023年5月24日 下午4:30

  function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
      // 边界判断
      if (list1 === null) {
          return list2
      }
      if (list2 === null) {
          return list1
      }
  
      while(list1 !== null && list2 !== null) {
          if (list1.val <= list2.val) {
              list1.next = mergeTwoLists(list1.next, list2)
              return list1
          } else {
              list2.next = mergeTwoLists(list1, list2.next)
              return list2
          }
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 小趴菜 永久会员 2023年5月18日 下午7:11

  class Solution {
  public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  if(list1null){
  return list2;
  }
  if(list2null){
  return list1;
  }
  //相当于拿list2当主链表
  if(list1.val>list2.val){
  list2.next = mergeTwoLists(list1,list2.next);
  return list2;
  }
  //相当于拿list1当主链表
  else{
  list1.next = mergeTwoLists(list1.next,list2);
  return list1;
  }
  }
  }

  0 赞同 0 条回复

  登录以回复
• mpweixin用户 永久会员 2023年4月29日 下午8:34

  //递归解法
  class Solution {
      public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
          if(list1 == null)
              return list2;
          else if(list2 == null)
              return list1;
          else if(list1.val < list2.val)
          {
              list1.next = mergeTwoLists(list1.next, list2);
              return list1;
          }
          else
          {
              list2.next = mergeTwoLists(list1, list2.next);
              return list2;
          }
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 庄重 普通 2023年4月26日 下午1:14

  class Solution {
  public:
      // 返回合并后的节点
      ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { 
  
          // 结束条件
          if(list1 == nullptr || list2 == nullptr) {
              return list2 == nullptr ? list1 : list2;
          }
  
          // 关系式
          if(list1->val > list2->val) {
              list2->next = mergeTwoLists(list1, list2->next);
              return list2; 
          }else {
              list1->next = mergeTwoLists(list1->next, list2);
              return list1;
          }
          // return list1->val > list2->val ? list2 : list1;
      }
  };
  // 时间复杂度O(2n); n为两个链表中较小的那个链表长度
  // 空间复杂度O(2n); n为两个链表中较小的那个链表长度
  

  0 赞同 0 条回复

  登录以回复
• 秊 永久会员 2023年4月23日 上午8:24

  时间：$O(m + n)$
  空间：$O(1)$

  class Solution {
      public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
          if (null == list1) return list2;
          if (null == list2) return list1;
  
          if (list1.val < list2.val) {
              list1.next = mergeTwoLists(list1.next, list2);
              return list1;
          } else {
              list2.next = mergeTwoLists(list1, list2.next);
              return list2;
          }
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 是梦终空 永久会员 2023年4月20日 下午12:48

  时间O(n)

  class Solution {
      public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
          //判断非空
          if(list1 == null){
              return list2;
          }
          if(list2 == null){
              return list1;
          }
          //1的值大于2
          if(list1.val > list2.val){
              list2.next = mergeTwoLists(list1,list2.next);
              return list2;
          }else{
              list1.next  = mergeTwoLists(list1.next,list2);
              return list1;
          }
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 小肸 永久会员 2023年4月19日 下午4:05

  class Solution {
      //递归函数：返回已经合并两个有序链表的新链表的头节点
      public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
          if (list1 == null) {
              return list2;
          }
          if (list2 == null) {
              return list1;
          }
          if (list1.val > list2.val) {
              list2.next = mergeTwoLists(list1, list2.next);
              return list2;
          } else {
              list1.next = mergeTwoLists(list1.next, list2);
              return list1;
          }
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• Everglow 永久会员 2023年4月18日 下午11:49

  class Solution {
      //返回合并后的有序链表
      public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
          //终止条件
          if(list1 == null) {
              return list2;
          }
          if(list2 == null) {
              return list1;
          }
          //递归公式
          if(list1.val <= list2.val) {
              list1.next = mergeTwoLists(list1.next, list2);
              return list1;
          } else {
              list2.next = mergeTwoLists(list1, list2.next);
              return list2;
          }
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• C++小将 永久会员 2023年4月18日 下午9:15

  打卡

  时间复杂度O(m+n),空间复杂度O(m+n)

  class Solution {
  public:
      ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
          if(!list1) return list2;
          if(!list2) return list1;
          if(list1->val < list2->val) {
              list1->next = mergeTwoLists(list1->next, list2);
              return list1;
          } else {
              list2->next = mergeTwoLists(list1, list2->next);
              return list2;
          }
      }
  
  };
  

  0 赞同 0 条回复

  登录以回复