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

  • RodneyShag
     + 11 comments

    O(1) space complexity Java solution

    From my HackerRank solutions.

    Runtime: O(n +m)
    Space Complexity: O(1)

    Any recursive solution will take at least O(n+m) space due to O(n+m) recursive calls. Try to do it iteratively for a more space efficient solution.

    Node MergeLists(Node currA, Node currB) {
    if (currA == null) {
        return currB;
    } else if (currB == null) {
        return currA;
    }
    
    /* Find new head pointer */
    Node head = null;
    if (currA.data < currB.data) {
        head = currA;
        currA = currA.next;
    } else {
        head = currB;
        currB = currB.next;
    }
    
    /* Build rest of list */
    Node n = head;
    while (currA != null && currB != null) {
        if (currA.data < currB.data) {
            n.next = currA;
            currA = currA.next;
        } else {
            n.next = currB;
            currB = currB.next;
        }
        n = n.next;
    }
    
    /* Attach the remaining elements */
    if (currA == null) {
        n.next = currB;
    } else {
        n.next = currA;
    }

    return head;
}

    Let's try an example

    List A: 1 -> 4 -> null
List B: 2 -> null

Created: null

    Now the code labeled Find new head pointer will give us the following result: 

    List A: 4 -> null
List B: 2 -> null

Created: 1 -> null

    The code labeled Build rest of list will then give us:

    List A: 4 -> null
List B: null

Creaetd: 1 -> 2

    Finally, the code labeled Attach the remaining elements will complete our list:

    List A: null
List B: null

Created: 1 -> 2 -> 4

    Let me know if you have any questions.