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/
See Question&Answers more detail:os