数据结构 将两个有序的链表合并为一个新链表

问题描述

将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的，且合并后新链表依然有序。 比如{1，4} {3，5}，合并就是{1，3，4，5}；

解题思路

首先我们要判定是否有一个链表为空，都为空，返回空，一个为空，则返回不为空的那个；其次找到，两个链表的第一个节点，比较小的那个，作为主链（head），将另一个的节点元素，依次比较，并入其中，最后肯定有一个链表先走完，那么只需要把未走完后续链表并入就好了。

代码展示

public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
          
   
        // write code here
      if(l1 == null) return l2;
      if(l2 == null) return l1;
      //先处理头
      ListNode head = (l1.val <= l2.val)? l1:l2;
      ListNode tail = head;
      l1 = (head == l1)? l1.next:l1;
      l2 = (head == l2)? l2.next:l2;
      while(l1 != null && l2 != null)
      {
          
   
          if(l1.val <= l2.val){
          
   
              tail.next = l1;
              l1 = l1.next;
          }else{
          
   
              tail.next = l2;
              l2 = l2.next;
          }
          tail = tail.next;
      }
      tail.next = (l1 == null)? l2 : l1;
      return head;
    }