Merging Two Sorted Linked Lists

Merging Two Sorted Linked Lists

Problem

You’re given two sorted linked lists. The goal is to merge them into a single sorted list by rearranging the existing nodes.

---

Strategy

I stopped thinking about linked lists and treated it like merging two sorted sequences.

At each step:

• Compare the current nodes
• Pick the smaller one
• Move forward in that list

Repeat this until one list is finished, then attach whatever is left.

Code

class Solution:
    def mergeTwoLists(self, list1, list2):
        dummy = ListNode()
        current = dummy

        while list1 and list2:
            if list1.val < list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next

            current = current.next

        current.next = list1 if list1 else list2
        return dummy.next

Key Lines Explained

• dummy = ListNode()
  This avoids dealing with special cases for the first node.

• if list1.val < list2.val:
  This is the main decision point that keeps the list sorted.

• current.next = list1 (or list2)
  We are not creating new nodes, just linking existing ones.

• current = current.next
  Move forward after adding a node.

• current.next = list1 if list1 else list2
  Once one list ends, attach the rest of the other list directly.

Complexity

• Time: O(n + m)
• Space: O(1)

Final Note

The problem becomes simple once you stop overcomplicating it. It’s just about consistently picking the next smallest element and moving forward.