**Description**Hints**Submissions**Solutions

Total Accepted: 221656 Total Submissions: 571422 Difficulty: Easy Contributor: LeetCode

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.

Hide Company Tags  Amazon LinkedIn Apple Microsoft Hide Tags  Linked List Hide Similar Problems  (H) Merge k Sorted Lists (E) Merge Sorted Array (M) Sort List (M) Shortest Word Distance II

** 解题思路** recursive 递归解法。 类似merge two sorted array

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
      // use recursive 
      if (l2 == null)  return l1;
      if (l1 == null)  return l2;
      
      ListNode mergeHead;
      
      if (l1.val < l2.val) {
          mergeHead = l1;
          mergeHead.next = mergeTwoLists(l1.next, l2);
      } else {
          mergeHead = l2;
          mergeHead.next = mergeTwoLists(l1, l2.next);
      }
      return mergeHead;
    }
    
    public ListNode mergeTwoListsFailed(ListNode l1, ListNode l2) {
        ListNode p1 = l1;
        ListNode p2 = l2 ;
        ListNode p = new ListNode(0);
        
        
        while (p1 != null && p2 != null) {
            // p.next = (p1.val > p2.val) ? new ListNode(p1.val) : new ListNode(p2.val);
            if (p1.val > p2.val) {
                p.next = new ListNode(p1.val);
                p1 = p1.next;
            } else {
                p.next = new ListNode(p2.val);
                p2 = p2.next;
            }
         
        }
        
        while (p2 != null) {
          p.next = new ListNode(p2.val);
          p2 = p2.next;
         
        }
        
        while (p1 != null) {
            p.next = new ListNode(p1.val);
            p1 = p1.next;
          
        }
        return p;
    }
}