## Introduction – Merging two Sorted Singly Linked List

This question is mostly asked in interviews and hence I thought of writing few possible solutions to the same. I also asked the same question on stackoverflow.com. You can visit the link here

## Problem Statement

You have two singly linked lists that are already sorted, you have to merge them and return the head of the new list without creating any new extra nodes. The returned list should be sorted as well

The method signature is:

1 |
Node MergeLists(Node list1, Node list2); |

Node class is below:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Node{ int data; Node next; public Node(){ } public Node(int data, Node next){ this(); this.data = data; this.next = next; } public int getData(){ return this.data; } public Node getNext(){ return this.next; } public void setData(int data){ this.data = data; } public void setNext(Node next){ this.next = next; } } |

## Solution

There can be multiple solutions to the given problem, few of them are given below:

## Recursive Solution

1 2 3 4 5 6 7 8 9 10 11 12 |
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; } } |

## Without Recursion

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
Node MergeLists(Node list1, Node list2) { if (list1 == null) return list2; if (list2 == null) return list1; Node head; if (list1.data < list2.data) { head = list1; } else { head = list2; list2 = list1; list1 = head; } while(list1.next != null && list2 != null) { if (list1.next.data <= list2.data) { list1 = list1.next; } else { Node tmp = list1.next; list1.next = list2; list2 = tmp; } } if (list1.next == null) list1.next = list2; return head; } |

## Conclusion

Here we learnt to merge two sorted singly linked list without creating any another list. This problem can be solved using recursion, which I personally like. For the non-recursion lovers there is another program written above.

Hope this helps. Stay connected and stay Subscribed