Merge Two Sorted Lists leetcode java

题目：

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;

     }

巴特西

Merge Two Sorted Lists leetcode java

最新文章

热门文章