Algorithms to Compute the Interleaved Linked List

Given two linked lists l0 and l1, return the two linked lists interleaved, starting with l0. If there are leftover nodes in a linked list, they should be added to the end.

Constraints
n ≤ 100,000 where n is the number of nodes in l0
m ≤ 100,000 where m is the number of nodes in l1
Example 1
Input
l0 = [7, 8]
l1 = [1, 2]
Output
[7, 1, 8, 2]

Example 2
Input
l0 = [7, 8]
l1 = [1]
Output
[7, 1, 8]

Interleaved Linked List by Recursion

We can interleave two linked lists by Recursion. If one of the Linked List is empty, we simply return another one. Otherwise, we connect l0 to l1 and l1 to original l0’s next. Then, we can solve a smaller problem via Recursion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
LLNode* solve(LLNode* l0, LLNode* l1) {
    if (!l0) return l1;
    if (!l1) return l0;
    auto l0next = l0->next;
    auto l1next = l1->next;
    l0->next = l1;
    l1->next = solve(l0next, l1next);
    return l0;
}

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
LLNode* solve(LLNode* l0, LLNode* l1) {
    if (!l0) return l1;
    if (!l1) return l0;
    auto l0next = l0->next;
    auto l1next = l1->next;
    l0->next = l1;
    l1->next = solve(l0next, l1next);
    return l0;
}

The time complexity is O(M+N) where M and N are the lengths of two linked list respectively.

Interleaved Linked List by Iterative Algorithm

We can do this also iteratively. Advance two pointers (current and successor) respectively until we don’t have any successor.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
LLNode* solve(LLNode* l0, LLNode* l1) {
    if (!l0) return l1;
    if (!l1) return l0;
    LLNode *curr = l0, *succ = l1, *temp;
    while (succ) {
        temp = curr->next;
        curr = curr->next = succ;
        succ = temp;
    }
    return l0;
}

/**
 * class LLNode {
 *     public:
 *         int val;
 *         LLNode *next;
 * };
 */
LLNode* solve(LLNode* l0, LLNode* l1) {
    if (!l0) return l1;
    if (!l1) return l0;
    LLNode *curr = l0, *succ = l1, *temp;
    while (succ) {
        temp = curr->next;
        curr = curr->next = succ;
        succ = temp;
    }
    return l0;
}

The time complexity is also O(N+M), and the space complexity is O(1).

–EOF (The Ultimate Computing & Technology Blog) —