We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Linked Lists
  4. Merge two sorted linked lists
  5. Discussions

Merge two sorted linked lists

  • Prashantkr314
     + 2 comments

    Essentially the same thing but little clean and easy to understand

    /*      class Node {
            int data;
            Node next;
          }
*/

Node mergeLists(Node headA, Node headB) {
    Node a = headA;
    Node b = headB;
    Node c = null;
    
    if(a == null || b == null)  // either of them is null
        return a == null? b:a;
    
    // getting the first index pointed by c, done this so now in the coming loop i can use next directly on c
    
     if(a.data < b.data ){
            c = a;
            a = a.next;
        }else{
            c = b;
            b = b.next;
        }
    Node head = c;
    
    
    // either one of a or b has been changed,
    
    while(a != null && b != null){ // ie going to the last elements of the linked lists
        if(a.data < b.data ){
            c.next = a;
            a = a.next;
        }else{
            c.next = b;
            b = b.next;
        }
        c = c.next;
    }
    
    // either one of a and b is finished
    
    // a is left
    if(a != null)
        c.next = a;
 
    
    // b is left
    if(b != null)
        c.next = b;
    
    return head;
}