Interview Question: Merge two sorted singly linked lists without creating new nodes

Question

This is a programming question asked during a written test for an interview. "You have two singly linked lists that are already sorted, you have to merge them and return a the head of the new list without creating any new extra nodes. The returned list should be sorted as well"

The method signature is: Node MergeLists(Node list1, Node list2);

Node class is below:

class Node{
    int data;
    Node next;
}

I tried many solutions but not creating an extra node screws things. Please help.

Here is the accompanying blog entry http://techieme.in/merging-two-sorted-singly-linked-list/

Answer 1

Node MergeLists(Node list1, Node list2) {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

  if (list1.data < list2.data) {
    list1.next = MergeLists(list1.next, list2);
    return list1;
  } else {
    list2.next = MergeLists(list2.next, list1);
    return list2;
  }
}