Prab's Code Blog

Because talk is cheap, show me the code!

Elegant Solutions to Common Interview Problems - Part 1 - Linked Lists

Define a linked list node for integers

LinkedListNode.cpp
1
2
3
4
5
class Node {
    public:
    int data;
    Node* next;
};

Reverse a singly linked list in-place iteratively

ReverseLinkedListIterative.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Node* reverseIterative(Node* head) {
    // Empty list is already reversed
    if (!head) {
        return NULL;
    }
    // Initialize two pointers, current(ptr) and previous
    Node* ptr = head;
    Node* prev = NULL;
    // At each node, we point it's next to previous
    while (ptr) {
        Node* next = ptr->next;
        ptr->next = prev;
        // Advance both pointers
        prev = ptr;
        ptr = next;
    }
    // Point head to last node
    head = prev;
    return head;
}

Reverse a singly linked list in-place recursively

ReverseLinkedListRecursive.cpp
1
2
3
4
5
6
7
8
9
10
Node* reverseRecursive(Node* head) {
    if (!head || !head->next) {
        return head;
    }
    Node* rest = reverseRecursive(head->next);
    // Point head's next node towards head
    head->next->next = head;
    head->next = NULL;
    return rest;
}

Traverse a linked list recursively

traverseRecursive.cpp
1
2
3
4
5
6
7
8
void traverse(Node* head) {
    if (!head) {
        return;
    } else {
        cout<<head->data<<endl;
    }
    traverse(head->next);
}

Traverse a linked list recursively in reverse order

traverseRecursiveReverse.cpp
1
2
3
4
5
6
7
void traverseReverse(Node* head) {
    if (!head) {
        return;
    }
    traverseReverse(head->next);
    cout<<head->data<<endl;
}

Print nth element of linked list (counted from 1)

printNthElement.cpp
1
2
3
4
5
6
7
8
9
void printNthElement(Node* head, int n) {
    if (!head) {
        return;
    }
    if (n == 1) {
        cout<<head->data;
    }
    printNthElement(head->next, n-1);
}

Print nth element from last in linked list

printNthElementFromLast.cpp
1
2
3
4
5
6
7
8
9
10
11
void printNthLastElement(Node* head, int* n) {
    if (!head) {
        return;
    }
    printNthLastElement(head->next, n);
    *n = *n - 1;
    if (*n == 0) {
        cout<<head->data;
        return;
    }
}

Comments