Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

/*
Definition for singly-linked list.

public class Node {
  int val;
  Node next;
  Node(int x) { val = x; }
}
*/

public class Solution {
  public Node merge(Node l1, Node l2) {

  }
}

This problem is selected from LeetCode.

Solution

We could use two pointers l1 and l2 to track the current nodes of list 1 and list2. Then traverse the two linked list node by node. Each time choose the node with the smaller value between l1.val and l2.val and append the node to the end of the new list. Then move the selected pointer to the next node of its list. Notice that, if the two lists do not have the same size, in the end, we need to append the remaining nodes of the longer list to the tail of the new list.

public Node merge(Node l1, Node l2) {

  if(l1 == null) {
    return l2;
  }else if(l2 == null){
    return l1;
  }

  // a dummy node as the head of
  // the new linked list.
  Node head = new Node(0);

  Node tail = head;

  while(l1 != null && l2 != null){
    if(l1.val < l2.val){
      tail.next = new Node(l1.val);
      l1 = l1.next;
    }else{
      tail.next = new Node(l2.val);
      l2 = l2.next;
    }

    tail = tail.next;
  }

  // add the remaining l1 or l2
  // to the tail.
  tail.next = (l1 != null)?l1:l2;

  return head.next;
}

RelatedPost