Merge Two Sorted Lists leetcode java

时间:2022-06-01 21:46:00

题目:

Merge two sorted linked lists and return it as a new list. The new list
should be made by splicing together the nodes of the first two lists.

题解:

这道题是链表操作题,题解方法很直观。

首先,进行边界条件判断,如果任一一个表是空表,就返回另外一个表。

然后,对于新表选取第一个node,选择两个表表头最小的那个作为新表表头,指针后挪。

然后同时遍历两个表,进行拼接。

因为表已经是sorted了,最后把没有遍历完的表接在新表后面。

由于新表也会指针挪动,这里同时需要fakehead帮助记录原始表头。

代码如下:

 1     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
 2         if(l1==null)
 3             return l2;
 4         if(l2==null)
 5             return l1;
 6             
 7         ListNode l3;
 8         if(l1.val<l2.val){
 9             l3 = l1;
             l1 = l1.next;
         }else{
             l3 = l2;
             l2 = l2.next;
         }
         
         ListNode fakehead = new ListNode(-1);
         fakehead.next = l3;
         while(l1!=null&&l2!=null){
             if(l1.val<l2.val){
                 l3.next = l1;
                 l3 = l3.next;
                 l1 = l1.next;
             }else{
                 l3.next = l2;
                 l3 = l3.next;
                 l2 = l2.next;
             }
         }
         
         if(l1!=null)
             l3.next = l1;
         if(l2!=null)
             l3.next = l2;
         return fakehead.next;
     }

更简便的方法是,不需要提前选新表表头。

对于新表声明两个表头,一个是fakehead,一个是会挪动的指针,用于拼接。同时,边界条件在后面的补拼中页解决了,所以开头没必要做边界判断,这样代码简化为:

 1     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
 2         ListNode fakehead = new ListNode(-1);
 3         ListNode l3 = fakehead;
 4         while(l1!=null&&l2!=null){
 5             if(l1.val<l2.val){
 6                 l3.next = l1;
 7                 l3 = l3.next;
 8                 l1 = l1.next;
 9             }else{
                 l3.next = l2;
                 l3 = l3.next;
                 l2 = l2.next;
             }
         }
         
         if(l1!=null)
             l3.next = l1;
         if(l2!=null)
             l3.next = l2;
         return fakehead.next;
     }