21. Merge Two Sorted Lists

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.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 class Solution {
10     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
11         ListNode dummy = new ListNode(0);
12         ListNode p1 = l1, p2 = l2, p = dummy;
13         for (;p1 != null && p2 != null; p = p.next) {
14             if (p1.val < p2.val) {
15                 p.next = new ListNode(p1.val);
16                 p1 = p1.next;
17             } else {
18                 p.next = new ListNode(p2.val);
19                 p2 = p2.next;
20             }
21         }
22         
23         while (p1 != null) {
24             p.next = new ListNode(p1.val);
25             p = p.next;
26             p1 = p1.next;
27             
28         }
29         
30         while (p2 != null) {
31             p.next = new ListNode(p2.val);
32             p = p.next;
33             p2 = p2.next;
34         }
35         
36         return dummy.next;
37     }
38 }