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

User · Accepted Answer

Node MergeLists Node list1  Node list2      if  list1    null  return list2    if  list2    null  return list1     if  list1 data  lt  list2 data        list1 next   MergeLists list1 next  list2       return list1      else       list2 next   MergeLists list2 next  list1       return list2

User · Answer

Node MergeLists Node list1  Node list2          if list is null return other list     if list1    null             return list2          else if list2    null             return list1          else              Node head            Take head pointer to the node which has smaller first data node         if list1 data  lt  list2 data                        head   list1              list1   list1 next                    else                      head   list2             list2   list2 next                    Node current   head            loop till both list are not pointing to null         while list1    null    list2    null                          if list1 is null  point rest of list2 by current pointer              if list1    null                  current next   list2                 return head                              if list2 is null  point rest of list1 by current pointer              else if list2    null                  current next   list1                 return head                              compare if list1 node data is smaller than list2 node data  list1 node will be               pointed by current pointer             else if list1 data  lt  list2 data                                current next   list1                  current   current next                  list1   list1 next                            else                               current next   list2                  current   current next                  list2   list2 next                                    return head

User · Answer

A simple iterative solution   Node  MergeLists Node  A  Node  B          handling the corner cases        if both lists are empty     if  A  amp  amp   B                cout  lt  lt   List is empty   lt  lt  endl          return 0              either of list is empty     else if  A  return B      else if  B  return A      else               Node  head   NULL   this will be the head of the newList         Node  previous   NULL   this will act as the             In this algorithm we will keep the          previous pointer that will point to the last node of the output list           And  as given we have A  amp  B as pointer to the given lists            The algorithm will keep on going untill either one of the list become empty           Inside of the while loop  it will divide the algorithm in two parts              - First  if the head of the output list is not obtained yet             - Second  if head is already there then we will just compare the values and keep appending to the  previous  pointer           When one of the list become empty we will append the other  left over  list to the output list                       while A  amp  amp  B                          if  head                                  if A- gt data  lt   B- gt data                                          head   A   setting head of the output list to A                      previous   A    initializing previous                      A   A- gt next                                      else                                         head   B   setting head of the output list to B                      previous   B   initializing previous                      B   B- gt next                                                 else  when head is already set                                 if A- gt data  lt   B- gt data                                          if previous- gt next    A                           previous- gt next   A                       A   A- gt next   Moved A forward but keeping B at the same position                                     else                                         if previous- gt next    B                           previous- gt next   B                       B   B- gt next    Moved B forward but keeping A at the same position                                     previous   previous- gt next   Moving the Output list pointer forward                                     at the end either one of the list would finish           and we have to append the other list to the output list         if  A              previous- gt next   B           if  B              previous- gt next   A           return head    returning the head of the output list

User · Answer

Look ma  no recursion   struct llist   llist merge struct llist  one  struct llist  two  int   cmp  struct llist  l  struct llist  r      struct llist  result    tail   for  result NULL  tail    amp result  one  amp  amp  two  tail    amp   tail - gt next             if  cmp one two   lt  0     tail   one  one one- gt next            else    tail   two  two two- gt next               tail   one   one  two  return result

User · Answer

My take on the question is as below   Pseudocode   Compare the two heads A and B   If A  lt   B  then add A and move the head of A to the next node   Similarly  if B  lt  A  then add B and move the head of B to the next node B  If both A and B are NULL then stop and return  If either of them is NULL  then traverse the non null head till it becomes NULL    Code   public Node mergeLists Node headA  Node headB        Node merge   null         If we have reached the end  then stop      while  headA    null    headB    null               if B is null then keep appending A  else check if value of A is lesser or equal than B         if  headB    null     headA    null  amp  amp  headA data  lt   headB data                    Add the new node  handle addition separately in a new method              merge   add merge  headA data                  Since A is  lt   B  Move head of A to next node             headA   headA next             if A is null then keep appending B  else check if value of B is lesser than A           else if  headA    null     headB    null  amp  amp  headB data  lt  headA data                    Add the new node  handle addition separately in a new method              merge   add merge  headB data                  Since B is  lt  A  Move head of B to next node             headB   headB next                      return merge     public Node add Node head  int data        Node end   new Node data       if  head    null            return end             Node curr   head      while  curr next    null            curr   curr next             curr next   end      return head

User · Answer

Common code for insert at the end         private void insertEnd int data                    Node newNode   new Node data                   if  head    null                        newNode next   head                      head   tail   newNode                      return                                    Node tempNode   tail                  tempNode next   newNode                  tail   newNode                     private void mergerTwoSortedListInAscOrder Node tempNode1  Node tempNode2                 if  tempNode1    null  amp  amp  tempNode2    null                  return              if  tempNode1    null                    head3   tempNode2                  return                            if  tempNode2    null                    head3   tempNode1                  return                             while  tempNode1    null  amp  amp  tempNode2    null                     if  tempNode1 mData  lt  tempNode2 mData                        insertEndForHead3 tempNode1 mData                       tempNode1   tempNode1 next                    else if  tempNode1 mData  gt  tempNode2 mData                        insertEndForHead3 tempNode2 mData                       tempNode2   tempNode2 next                    else                       insertEndForHead3 tempNode1 mData                       insertEndForHead3 tempNode2 mData                       tempNode1   tempNode1 next                      tempNode2   tempNode2 next                                               if  tempNode1    null                    while  tempNode1    null                        insertEndForHead3 tempNode1 mData                       tempNode1   tempNode1 next                                              if  tempNode2    null                    while  tempNode2    null                        insertEndForHead3 tempNode2 mData                       tempNode2   tempNode2 next                                                GlbMP

User · Answer

Recursive way variant of Stefan answer    MergeList Node nodeA  Node nodeB            if nodeA  null  return nodeB           if nodeB  null  return nodeA        if nodeB data lt nodeA data           Node returnNode   MergeNode nodeA nodeB next           nodeB next   returnNode          retturn nodeB       else          Node returnNode   MergeNode nodeA next nodeB           nodeA next returnNode          return nodeA          Consider below linked list to visualize this  2 gt 4 list A 1 gt 3  list B  Almost same answer non recursive  as Stefan but with little more comments meaningful variable name  Also covered double linked list in comments if someone is interested  Consider the example  5- gt 10- gt 15 gt 21      List1  2- gt 3- gt 6- gt 20      List2  Node MergeLists List list1  List list2      if  list1    null  return list2    if  list2    null  return list1   if list1 head data gt list2 head data     listB  list2     loop over this list as its head is smaller   listA  list1    else     listA  list2     loop over this list   listB  list1      listB currentNode listB head  listA currentNode listA head   while listB currentNode  null      if listB currentNode data lt listA currentNode data       Node insertFromNode   listB currentNode prev       Node startingNode   listA currentNode      Node temp   inserFromNode next      inserFromNode next   startingNode      startingNode next temp       startingNode next prev  startingNode     for doubly linked list     startingNode prev inserFromNode      for doubly linked list       listB currentNode  listB currentNode next      listA currentNode  listA currentNode next          else         listB currentNode  listB currentNode next

User · Answer

Simple code in javascript to merge two linked list inplace  function mergeLists l1  l2        let head   new ListNode 0     dummy     let curr   head      while l1  amp  amp  l2            if l2 val  gt   l1 val                curr next   l1              l1   l1 next            else               curr next   l2              l2 l2 next                   curr   curr next            if  l1           curr next l2            if  l2           curr next l1             return head next

User · Answer

I would like to share how i thought the solution    i saw the solution that involves recursion and they are pretty amazing  is the outcome of well functional and modular thinking  I really appreciate the sharing   I would like to add that recursion won t work for big lits  the stack calls will overflow  so i decided to try the iterative approach    and this is what i get    The code is pretty self explanatory  i added some inline comments to try to assure this   If you don t get it  please notify me and i will improve the readability  perhaps i am having a misleading interpretation of my own code    import java util Random    public class Solution        public static class Node lt T extends Comparable lt   super T gt  gt  implements Comparable lt Node lt T gt  gt             T data          Node next            Override         public int compareTo Node lt T gt  otherNode                return data compareTo otherNode data                       Override         public String toString                 return   data    null    data toString       next    null          next toString            null                         public static Node merge Node firstLeft  Node firstRight            combine firstLeft  firstRight           return Comparision perform firstLeft  firstRight  min              private static void combine Node leftNode  Node rightNode            while  leftNode    null  amp  amp  rightNode    null                   get comparision data about  current pair of nodes being analized               Comparision comparision   Comparision perform leftNode  rightNode                  stores references to the next nodes             Node nextLeft   leftNode next               Node nextRight   rightNode next                 set the  next node  of the  minor node  between the  current pair of nodes being analized                       to be equals the minor node between the  major node  and  the next one of the minor node  of the former comparision              comparision min next   Comparision perform comparision max  comparision min next  min              if  comparision min    leftNode                    leftNode   nextLeft                else                   rightNode   nextRight                                     Stores references to two nodes viewed as one minimum and one maximum  The static factory method populates properly the instance being build        private static class Comparision            private final Node min          private final Node max           private Comparision Node min  Node max                this min   min              this max   max                     private static Comparision perform Node a  Node b                Node min  max              if  a    null  amp  amp  b    null                    int comparision   a compareTo b                   if  comparision  lt   0                        min   a                      max   b                    else                       min   b                      max   a                                  else                   max   null                  min    a    null    a   b                            return new Comparision min  max                       Test example         public static void main String args              Node firstLeft   buildList 20           Node firstRight   buildList 40           Node firstBoth   merge firstLeft  firstRight           System out println firstBoth             someone need to write something like this i guess        public static Node buildList int size            Random r   new Random            Node lt Integer gt  first   new Node lt  gt             first data   0          first next   null          Node lt Integer gt  current   first          Integer last   first data          for  int i   1  i  lt  size  i                  Node lt Integer gt  node   new Node lt  gt                 node data   last   r nextInt 5               last   node data              node next   null              current next   node              current   node                    return first

User · Answer

public static Node merge Node h1  Node h2         Node h3   new Node 0       Node current   h3       boolean isH1Left   false      boolean isH2Left   false       while  h1    null    h2    null            if  h1 data  lt   h2 data                current next   h1              h1   h1 next            else               current next   h2              h2   h2 next                    current   current next           if  h2    null  amp  amp  h1    null                isH1Left   true              break                     if  h1    null  amp  amp  h2    null                isH2Left   true              break                       if  isH1Left            while  h1    null                current next   h1              current   current next              h1   h1 next                        if  isH2Left            while  h2    null                current next   h2              current   current next              h2   h2 next                       h3   h3 next       return h3

User · Answer

First of all understand the mean of  without creating any new extra nodes   As I understand it does not mean that I can not have pointer s  which points to an existing node s     You can not achieve it without talking pointers to existing nodes  even if you use recursion to achieve the same  system will create pointers for you as call stacks  It is just like telling system to add pointers which you have avoided in your code   Simple function to achieve the same with taking extra pointers    typedef struct  LLNode      int             value      struct  LLNode  next   LLNode    LLNode  CombineSortedLists LLNode  a LLNode  b       if NULL    a           return b            if NULL    b           return a            LLNode  root    NULL      if a- gt value  lt  b- gt value           root   a          a   a- gt next            else          root   b          b      b- gt next            LLNode  curr    root      while 1           if a- gt value  lt  b- gt value               curr- gt next   a              curr   a              a a- gt next              if NULL    a                   curr- gt next   b                  break                                  else              curr- gt next   b              curr   b              b b- gt next              if NULL    b                   curr- gt next   a                  break                                    return root

User · Answer

Node   merge sort Node  a  Node  b      Node  result   NULL     if a     NULL        return b     else if b    NULL        return a        For the first node  we would set the result to either a or b        if a- gt data  lt   b- gt data          result   a         Result s next will point to smaller one in lists         starting at a- gt next  and b          result- gt next   merge sort a- gt next b             else         result   b         Result s next will point to smaller one in lists         starting at a and b- gt next           result- gt next   merge sort a b- gt next             return result       Please refer to my blog post for http   www algorithmsandme com 2013 10 linked-list-merge-two-sorted-linked html

User · Answer

Here is the code on how to merge two sorted linked lists headA and headB   Node  MergeLists1 Node  headA  Node  headB        Node  p   headA      Node  q   headB      Node  result   NULL       Node  pp   NULL      Node  qq   NULL      Node  head   NULL      int value1   0      int value2   0      if  headA    NULL   amp  amp   headB    NULL                 return NULL            if headA  NULL                return headB            else if headB  NULL                return headA            else               while  p    NULL      q    NULL                         if  p    NULL   amp  amp   q    NULL                                 int value1   p- gt data                  int value2   q- gt data                  if value1  lt   value2                                        pp   p- gt next                      p- gt next   NULL                      if result    NULL                                                head   result   p                                            else                                               result- gt next   p                          result   p                                            p   pp                                    else                                       qq   q- gt next                      q- gt next   NULL                      if result    NULL                                                head   result   q                                            else                                               result- gt next   q                          result   q                                            q   qq                                              else                               if p    NULL                                        pp   p- gt next                      p- gt next   NULL                      result- gt next   p                      result   p                      p   pp                                    if q    NULL                                        qq   q- gt next                      q- gt next   NULL                      result- gt next   q                      result   q                      q   qq                                                      return head

User · Answer

Here is the algorithm on how to merge two sorted linked lists A and B   while A not empty or B not empty     if first element of A  lt  first element of B        remove first element from A       insert element into C    end if    else        remove first element from B       insert element into C end while   Here C will be the output list

User · Answer

This could be done without creating the extra node  with just an another Node reference passing to the parameters  Node temp    private static Node mergeTwoLists Node nodeList1  Node nodeList2  Node temp        if nodeList1    null  return nodeList2      if nodeList2    null  return nodeList1       if nodeList1 data  lt   nodeList2 data           temp   nodeList1          temp next   mergeTwoLists nodeList1 next  nodeList2  temp             else          temp   nodeList2          temp next   mergeTwoLists nodeList1  nodeList2 next  temp             return temp

User · Answer

Recursion should not be needed to avoid allocating a new node   Node MergeLists Node list1  Node list2      if  list1    null  return list2    if  list2    null  return list1     Node head    if  list1 data  lt  list2 data        head   list1      else       head   list2      list2   list1      list1   head        while list1 next    null        if  list1 next data  gt  list2 data          Node tmp   list1 next        list1 next   list2        list2   tmp            list1   list1 next         list1 next   list2    return head

User · Answer

Simple Elegant Iterative approach in Java               private static LinkedList mergeLists LinkedList list1  LinkedList list2                        Node head1   list1 start                      Node head2   list2 start                      if  list1 size    0                      return list2                      if  list2 size    0                      return list1                                     LinkedList mergeList   new LinkedList                        while  head1    null  amp  amp  head2    null                            if  head1 getData    lt  head2 getData                                  int data   head1 getData                                mergeList insert data                               head1   head1 getNext                              else                               int data   head2 getData                                mergeList insert data                               head2   head2 getNext                                                                        while  head1    null                            int data   head1 getData                            mergeList insert data                           head1   head1 getNext                                              while  head2    null                            int data   head2 getData                            mergeList insert data                           head2   head2 getNext                                              return mergeList                        Build-In singly LinkedList class in Java   class LinkedList       Node start      int size   0       void insert int data            if  start    null              start   new Node data           else               Node temp   start              while  temp getNext      null                    temp   temp getNext                              temp setNext new Node data                      size                Override     public String toString              String str               Node temp start          while  temp    null                str    temp getData      -- gt                temp   temp getNext                      return str

User · Answer

private static Node mergeLists Node L1  Node L2         Node P1   L1 val  lt  L2 val   L1   L2      Node P2   L1 val  lt  L2 val   L2   L1      Node BigListHead   P1      Node tempNode   null       while  P1    null  amp  amp  P2    null            if  P1 next    null  amp  amp  P1 next val  gt P2 val            tempNode   P1 next          P1 next   P2          P1   P2          P2   tempNode            else if P1 next    null           P1   P1 next          else           P1 next   P2          break                       return BigListHead

User · Answer

Node MergeLists Node node1  Node node2       if node1    null        return node2     else  node2    null        return node1      Node head     if node1 data  lt  node2 data             head   node1        node1   node1 next     else            head   node2        node2   node2 next           Node current   head     while  node1    null      node2    null              if  node1    null             current next   node2           return head                else if  node2    null             current next   node1           return head                 if  node1 data  lt  node2 data                    current next   node1            current   current next             node1   node1 next                else                   current next   node2            current   current next             node2   node2 next                  current next   NULL    needed to complete the tail of the merged list    return head

User · Answer

I show below an iterative solution  A recursive solution would be more compact  but since we don t know the length of the lists  recursion runs the risk of stack overflow   The basic idea is similar to the merge step in merge sort  we keep a pointer corresponding to each input list  at each iteration  we advance the pointer corresponding to the smaller element  However  there s one crucial difference where most people get tripped  In merge sort  since we use a result array  the next position to insert is always the index of the result array  For a linked list  we need to keep a pointer to the last element of the sorted list  The pointer may jump around from one input list to another depending on which one has the smaller element for the current iteration   With that  the following code should be self-explanatory   public ListNode mergeTwoLists ListNode l1  ListNode l2        if  l1    null            return l2            if  l2    null            return l1            ListNode first   l1      ListNode second   l2      ListNode head   null      ListNode last   null       while  first    null  amp  amp  second    null            if  first val  lt  second val                if  last    null                    last next   first                            last   first              first   first next            else               if  last    null                    last next   second                            last   second              second   second next                    if  head    null                head   last                       if  first    null            last next   second            if  second    null            last next   first             return head

User · Answer

I created only one dummy node at the beginning to save myself many  if  conditions       public ListNode mergeTwoLists ListNode l1  ListNode l2             ListNode list1Cursor   l1          ListNode list2Cursor   l2           ListNode currentNode   new ListNode -1      Dummy node         ListNode head   currentNode           while  list1Cursor    null  amp  amp  list2Cursor    null                        if  list1Cursor val  lt  list2Cursor val                    currentNode next   list1Cursor                  list1Cursor   list1Cursor next                  currentNode   currentNode next                else                   currentNode next   list2Cursor                  list2Cursor   list2Cursor next                  currentNode   currentNode next                                      Complete the rest         while  list1Cursor    null                currentNode next   list1Cursor              currentNode   currentNode next              list1Cursor   list1Cursor next                    while  list2Cursor    null                currentNode next   list2Cursor              currentNode   currentNode next              list2Cursor   list2Cursor next                     return head next

User · Answer

Iteration can be done as below  Complexity   O n   public static LLNode mergeSortedListIteration LLNode nodeA  LLNode nodeB        LLNode mergedNode       LLNode tempNode              if  nodeA    null            return nodeB                 if  nodeB    null            return nodeA                     if   nodeA getData    lt  nodeB getData                  mergedNode   nodeA          nodeA   nodeA getNext              else               mergedNode   nodeB          nodeB   nodeB getNext               tempNode   mergedNode        while  nodeA    null  amp  amp  nodeB    null                            if   nodeA getData    lt  nodeB getData                                         mergedNode setNext nodeA               nodeA   nodeA getNext                      else                       mergedNode setNext nodeB               nodeB   nodeB getNext                                             mergedNode   mergedNode getNext               if  nodeA    null                mergedNode setNext nodeA              if  nodeB    null                mergedNode setNext nodeB                    return tempNode

User · Answer

Node mergeList Node h1  Node h2        if  h1    null  return h2      if  h2    null  return h1      Node head      if  h1 data  lt  h2 data            head   h1        else           head   h2          h2   h1          h1   head             while  h1 next    null  amp  amp  h2    null            if  h1 next data  lt  h2 data                h1   h1 next            else               Node afterh2   h2 next              Node afterh1   h1 next              h1 next   h2              h2 next   afterh1               if  h2 next    null                    h2   afterh2                                    return head

User · Answer

void printLL        NodeLL cur   head      if cur getNext      null           System out println  LL is emplty         else            System out println  printing Node            while cur getNext      null               cur   cur getNext                System out print cur getData                               System out println       void mergeSortedList NodeLL node1  NodeLL node2       NodeLL cur1   node1 getNext        NodeLL cur2   node2 getNext         NodeLL cur   head      if cur1    null           cur   node2             if cur2    null           cur   node1                   while cur1    null  amp  amp  cur2    null            if cur1 getData    lt   cur2 getData                 cur setNext cur1               cur1   cur1 getNext                      else              cur setNext cur2               cur2   cur2 getNext                      cur   cur getNext                     while cur1    null           cur setNext cur1           cur1   cur1 getNext            cur   cur getNext                     while cur2    null           cur setNext cur2           cur2   cur2 getNext            cur   cur getNext                     printLL

User · Answer

Here is a complete working example that uses the linked list implemented java util  You can just copy paste the code below inside a main   method           LinkedList lt Integer gt  dList1   new LinkedList lt Integer gt             LinkedList lt Integer gt  dList2   new LinkedList lt Integer gt             LinkedList lt Integer gt  dListMerged   new LinkedList lt Integer gt              dList1 addLast 1           dList1 addLast 8           dList1 addLast 12           dList1 addLast 15           dList1 addLast 85            dList2 addLast 2           dList2 addLast 3           dList2 addLast 12           dList2 addLast 24           dList2 addLast 85           dList2 addLast 185            int i   0          int y   0          int dList1Size   dList1 size            int dList2Size   dList2 size            int list1Item   dList1 get i           int list2Item   dList2 get y           while  i  lt  dList1Size    y  lt  dList2Size                 if  i  lt  dList1Size                     if  list1Item  lt   list2Item    y  gt   dList2Size                        dListMerged addLast list1Item                       i                        if  i  lt  dList1Size                            list1Item   dList1 get i                                                                       if  y  lt  dList2Size                     if  list2Item  lt   list1Item    i  gt   dList1Size                        dListMerged addLast list2Item                       y                        if  y  lt  dList2Size                            list2Item   dList2 get y                                                                             for int x dListMerged                        System out println x

User · Answer

LLNode  mergeSorted LLNode  h1  LLNode  h2        LLNode  h3 NULL    LLNode  h3l    if h1  NULL  amp  amp  h2  NULL      return NULL     if h1  NULL       return h2     if h2  NULL       return h1     if h1- gt data lt h2- gt data           h3 h1      h1 h1- gt next         else           h3 h2       h2 h2- gt next         LLNode  oh h3    while h1  NULL  amp  amp  h2  NULL           if h1- gt data lt h2- gt data               h3- gt next h1        h3 h3- gt next        h1 h1- gt next              else              h3- gt next h2         h3 h3- gt next         h2 h2- gt next                 if h1  NULL      h3- gt next h2    if h2  NULL      h3- gt next h1    return oh

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

Examples related to algorithm

Examples related to singly-linked-list