LeetCode 21: Merge Two Sorted Lists.

Mar 24th, 2020
162
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*
2. Merge two sorted linked lists and return it as a new list.
3. The new list should be made by splicing together the nodes of the first two lists.
4.
5. Example:
6. --------
7. Input: 1->2->4, 1->3->4
8. Output: 1->1->2->3->4->4
9. */
10.
12. {
13.     public class ListNode
14.     {
15.         public int val;
16.         public ListNode next;
17.         public ListNode(int x) { this.val = x; }
18.     }
19.
20.     public class Solution
21.     {
22.         /// <summary>
23.         ///     Merges two sorted lists into one sorted list.
24.         ///     Time complexity : O(n)
25.         ///     Space complexity : O(1)
26.         /// </summary>
27.         /// <param name="l1">A ListNode object.</param>
28.         /// <param name="l2">A ListNode object.</param>
29.         public ListNode MergeTwoLists(ListNode l1, ListNode l2)
30.         {
31.             if (l1 == null)
32.                 return l2;
33.
34.             if (l2 == null)
35.                 return l1;
36.
37.             ListNode head = null, tail = null, current = null;
38.
39.             while (l1 != null && l2 != null)
40.             {
41.                 if (l1.val < l2.val)
42.                 {
43.                     current = l1;
44.                     l1 = l1.next;
45.                 }
46.                 else
47.                 {
48.                     current = l2;
49.                     l2 = l2.next;
50.                 }
51.
53.                 {
55.                     tail = current;
56.                 }
57.                 else
58.                 {
59.                     tail.next = current;
60.                     tail = tail.next;
61.                 }
62.             }
63.
64.             current = (l1 == null) ? l2 : l1;
65.
66.             while (current != null)
67.             {
68.                 tail.next = current;
69.                 current = current.next;
70.                 tail = tail.next;
71.             }
72.
73.             tail.next = null;
74.