Solutions

1. Two Pointers

O(n + m) time | O(1) space

Intuition

We can traverse through both lists with two pointers, taking the node with the smaller value at a time and moving its pointer.

Algorithm

Return the other list when either one is empty.
Create two pointers, each at the head of one of the lists.
Take the node with the smaller value as the head, move its pointer to the next node, and create a tail pointer at the head.
Traverse through both lists.
- Link the node with the smaller value to the tail and move its pointer to the next node.
- Move the tail to the next node.
Link whatever either pointer still has left to the tail.
Return the head.

1→ 2→ 4

1→ 3→ 4

1→ → → → →

1 = 1, take 1

1 / 7

Code

# Definitions:
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    if not list1:
        return list2
    if not list2:
        return list1
    if list1.val <= list2.val:
        head = list1
        list1 = list1.next
    else:
        head = list2
        list2 = list2.next
    tail = head
    while list1 and list2:
        if list1.val <= list2.val:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next
    tail.next = list1 or list2
    return head

// Definitions:
// function ListNode(val, next) {
//     this.val = val === undefined ? 0 : val
//     this.next = next === undefined ? null : next
// }

/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @returns {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  if (!list1) return list2
  if (!list2) return list1
  let head
  if (list1.val <= list2.val) {
    head = list1
    list1 = list1.next
  } else {
    head = list2
    list2 = list2.next
  }
  let tail = head
  while (list1 && list2) {
    if (list1.val <= list2.val) {
      tail.next = list1
      list1 = list1.next
    } else {
      tail.next = list2
      list2 = list2.next
    }
    tail = tail.next
  }
  tail.next = list1 || list2
  return head
}

// Definitions:
// class ListNode {
//     int val;
//     ListNode next;
//
//     ListNode() {}
//
//     ListNode(int val) {
//         this.val = val;
//     }
//
//     ListNode(int val, ListNode next) {
//         this.val = val;
//         this.next = next;
//     }
// }

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        ListNode head;
        if (list1.val <= list2.val) {
            head = list1;
            list1 = list1.next;
        } else {
            head = list2;
            list2 = list2.next;
        }
        ListNode tail = head;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        tail.next = list1 != null ? list1 : list2;
        return head;
    }
}