Merging two sorted linked lists

Question

suppose list 'A' is 1->3->5 and list 'B' is 4->6->7 how would you handle merging them with condition that they need to be sorted after merging I would like to share my view about this, please let me know if it needs improvement,

i) Compare first node of 'B' with each node of 'A'
while A.val<B.val
A=A.next
We get 'A' pointing to node whose value is lesser than node of 'B'
ii) As per the example, intent is to store '4' in '3' 's reference and prior to that store '3' 's reference in a temp

iii) The same will have to be done for nodes in 'A', as in '5' will have to be stored between 4 and 6

Please review this and help me in improvising

"Compare first node of 'B' with each node of 'A'." -- You only need to compare the heads. Remove the smallest head of A and B and append it to your result list. Repeat until one of A or B are empty. Append the other list to your result. — M Oehm, May 05 '17 at 08:26
@YvesDaoust thats the reason why I posted this question, to help me in completing this and improvising it — MrKickass, May 05 '17 at 08:38

score 1 · Accepted Answer · answered May 05 '17 at 09:01

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;
  }
}

From Interview: Merging two Sorted Singly Linked List

You are not going to find any clearer algo than this recursion I think.

If you want to go the iterative way, you also have another answer in the post I have linked to you.

score 0 · Answer 2 · answered Mar 29 '18 at 02:37

Besides the accepted answer, we could also solve this problem using iterative approach.

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) {
    if (list1.next.data > list2.data) {
      Node tmp = list1.next;
      list1.next = list2;
      list2 = tmp;
    }
    list1 = list1.next;
  } 
  list1.next = list2;
  return head;
}

Merging two sorted linked lists

2 Answers2