meta data for this page
  •  

Merge Two Sorted Lists

Leetcode

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one-sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

assets.leetcode.com_uploads_2020_10_03_merge_ex1.jpg 

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Solution 1

Solution 1

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  ListNode head = new ListNode();
  ListNode node = head;
  while (list1 != null || list2 != null) {
    node.next = new ListNode();
    node = node.next;
    if (list1 == null) {
      node.val = list2.val;
      list2 = list2.next;
    } else if (list2 == null) {
      node.val = list1.val;
      list1 = list1.next;
    } else {
      if (list1.val <= list2.val) {
        node.val = list1.val;
        list1 = list1.next;
      } else {
        node.val = list2.val;
        list2 = list2.next;
      }
    }
  }
  return head.next;
}