LeetCode - Algorithms - 21. Merge Two Sorted Lists

I am confused with pointer and linked list since I tounched computer as freshman in university.

just verify solution of other guys.

Java

Iterative

© LeetCode – Merge Two Sorted Lists (Java)

The key to solve the problem is defining a fake head. Then compare the first elements from each list. Add the smaller one to the merged list. Finally, when one of them is empty, simply append it to the merged list, since it is already sorted.

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		ListNode head = new ListNode(0);
		ListNode p = head;

		ListNode p1 = l1;
		ListNode p2 = l2;
		while (p1 != null && p2 != null) {
			if (p1.val < p2.val) {
				p.next = p1;
				p1 = p1.next;
			} else {
				p.next = p2;
				p2 = p2.next;
			}
			p = p.next;
		}

		if (p1 != null) {
			p.next = p1;
		}

		if (p2 != null) {
			p.next = p2;
		}

		return head.next;        
    }
}

Submission Detail

  • 208 / 208 test cases passed.
  • Runtime: 1 ms, faster than 20.84% of Java online submissions for Merge Two Sorted Lists.
  • Memory Usage: 40.2 MB, less than 12.09% of Java online submissions for Merge Two Sorted Lists.

Recursive

Java, 1 ms, 4 lines codes, using recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    	if (l1==null) return l2;
    	if (l2==null) return l1;
    	if (l1.val<l2.val) {
    		l1.next = mergeTwoLists(l1.next,l2);
    		return l1;
    	}
    	else {
    		l2.next = mergeTwoLists(l1,l2.next);
    		return l2;
    	}        
    }
}

Submission Detail

  • 208 / 208 test cases passed.
  • Runtime: 13 ms
  • Your runtime beats 34.74 % of java submissions.