Question
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.
Solution
The key to the solution here is to create a new linked list by creating a fake head.
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 public class Solution { 10 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 11 if (l2 == null) 12 return l1; 13 if (l1 == null) 14 return l2; 15 ListNode fakeHead = new ListNode(0); 16 ListNode tmp = fakeHead; 17 ListNode p1 = l1, p2 = l2; 18 while (p1 != null && p2 != null) { 19 if (p1.val < p2.val) { 20 tmp.next = p1; 21 p1 = p1.next; 22 } else { 23 tmp.next = p2; 24 p2 = p2.next; 25 26 } 27 tmp = tmp.next; 28 } 29 while (p1 != null) { 30 tmp.next = p1; 31 tmp = tmp.next; 32 p1 = p1.next; 33 } 34 while (p2 != null) { 35 tmp.next = p2; 36 tmp = tmp.next; 37 p2 = p2.next; 38 } 39 return fakeHead.next; 40 } 41 }