fueanta

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.  
  11. namespace Problems.LeetCode.LinkedList.MergeTwoSortedLists_21
  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.  
  52.                 if (head == null)
  53.                 {
  54.                     head = current;
  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.  
  75.             return head;
  76.         }
  77.     }
  78. }
RAW Paste Data