Merge Two Sorted Lists leetcode java

时间：2014-07-23 12:01:36 阅读：331 评论：0 收藏：0 [点我收藏+]

题目：

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;
10             l1 = l1.next;
11         }else{
12             l3 = l2;
13             l2 = l2.next;
14         }
15
16         ListNode fakehead = new ListNode(-1);
17         fakehead.next = l3;
18         while(l1!=null&&l2!=null){
19             if(l1.val<l2.val){
20                 l3.next = l1;
21                 l3 = l3.next;
22                 l1 = l1.next;
23             }else{
24                 l3.next = l2;
25                 l3 = l3.next;
26                 l2 = l2.next;
27             }
28         }
29
30         if(l1!=null)
31             l3.next = l1;
32         if(l2!=null)
33             l3.next = l2;
34         return fakehead.next;
35     }

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

对于新表声明两个表头，一个是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{
10                 l3.next = l2;
11                 l3 = l3.next;
12                 l2 = l2.next;
13             }
14         }
15
16         if(l1!=null)
17             l3.next = l1;
18         if(l2!=null)
19             l3.next = l2;
20         return fakehead.next;
21     }

Merge Two Sorted Lists leetcode java,布布扣,bubuko.com

Merge Two Sorted Lists leetcode java

原文：http://www.cnblogs.com/springfor/p/3862040.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)