首页 > 代码库 > Leetcode: Merge Two Sorted Lists

Leetcode: Merge Two Sorted Lists

2024-07-03 17:34:49   223人阅读

一点小错，两次过，基本思想是先比较头元素，哪个小就在哪个list的基础上插入，需要考虑两种不同的结束方式

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
14         if(l1 == null && l2 !=null) return l2;
15         if(l2 == null && l1 !=null) return l1;
16         if(l1 == null && l2 ==null) return null;
17         ListNode head1, head2, tail1, tail2;
18         if (l1.val < l2.val){
19             head1 = l1;
20             head2 = l2;
21         }
22         else {
23             head1 = l2;
24             head2 = l1;
25         }
26         tail1 = head1;
27         tail2 = head2;
28         while (tail1.next != null && tail2 != null){
29             if (tail1.next.val > tail2.val){
30                 ListNode n = new ListNode(tail2.val);
31                 n.next = tail1.next;
32                 tail1.next = n;
33                 tail1 = tail1.next;
34                 tail2 = tail2.next;
35             }
36             else {
37                 tail1 = tail1.next;
38             }
39         }
40         
41         if (tail1.next == null){ // end case1: tail1 reaches end before tail2
42             while (tail2 != null){
43                 ListNode n = new ListNode(tail2.val);
44                 tail1.next = n;
45                 tail1 = tail1.next;
46                 tail2 = tail2.next;
47             }
48         }
49         
50         //end case2: tail2 reaches end before tail1, no need to process
51         
52         return head1;
53     }
54 }

 别人的另外一种思路是，重新创建一个新的Linkedlist，把两个list的元素往里面插入，有很多细节很聪明，比如，第一个node建立为一个假的，ListNode dummyNode=new ListNode(Integer.MIN_VALUE), 最后返回dummyNode.next; 每次不new一个新的ListNode, 而是用已有的。

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
14         // Start typing your Java solution below
15         // DO NOT write main() function
16         
17         ListNode dummyNode = new ListNode(0);
18         ListNode currentNode = dummyNode;
19         
20         while(l1!=null||l2!=null){
21             if(l1!=null&&l2!=null)
22                 if(l1.val>l2.val){
23                     currentNode.next =l2;
24                     l2 = l2.next;
25                 }else{
26                     currentNode.next =l1;
27                     l1 = l1.next;
28                 }
29             else if(l1==null){
30                 currentNode.next =l2;
31                     l2 = l2.next;
32             }else{
33                 currentNode.next =l1;
34                     l1 = l1.next;
35             }
36             currentNode=currentNode.next;
37                        
38         }
39         return dummyNode.next;
40         
41     }
42 }

 


联系
我们