You are given the heads of two sorted linked lists, list1 and list2.\n\nMerge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.\n\nReturn the head of the merged linked list.\n\n### Constraints\n\n* The number of nodes in both lists is in the range [0, 50].\n* -100 <= Node.val <= 100.\n* Both list1 and list2 are sorted in non-decreasing order.\n\n### Example\n\n\nInput: list1 = [1,2,4], list2 = [1,3,4]\nOutput: [1,1,2,3,4,4]\n
Solution
Approach: Iterative with Dummy Node\n\nThis problem can be solved efficiently using an iterative approach with a dummy node to handle edge cases and simplify list construction.\n\n* Initialize: Create a dummy node (e.g., with value 0) and a current pointer, initially pointing to dummy. This dummy node will serve as a placeholder before the actual merged list begins.\n* Iterate and Compare: While both list1 and list2 are not None:\n * Compare the values of the current nodes (list1.val and list2.val).\n * Append the node with the smaller value to current.next.\n * Advance the pointer of the list from which the node was taken (e.g., if list1.val was smaller, list1 = list1.next).\n * Move current forward to current.next to prepare for the next node.\n* Append Remaining: After the loop, one of the lists might still have remaining nodes (because the other list became None). Append the entire remainder of that list to current.next. This handles cases where one list is longer or initially empty.\n* Return Result: The head of the merged list is dummy.next (since dummy was just a placeholder).\n\n### Python Code Solution\n\npython\n# Definition for singly-linked list.\nclass ListNode:\n def __init__(self, val=0, next=None):\n self.val = val\n self.next = next\n\ndef mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:\n dummy = ListNode()\n current = dummy\n\n while list1 and list2:\n if list1.val <= list2.val:\n current.next = list1\n list1 = list1.next\n else:\n current.next = list2\n list2 = list2.next\n current = current.next\n\n # Append the remaining part of list1 or list2\n if list1:\n current.next = list1\n elif list2:\n current.next = list2\n\n return dummy.next\n
