Solving Linked List Coding Problems

Solving Lined List coding problems with explanation

Photo by Aida L on Unsplash

C++ Definition

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

Problems

• Remove Duplicates from Sorted List Easy

Solution

1. Track previous node (node pointer in the code) of the node to be deleted.
2. Use tmp variable to point to the node to be deleted.
3. Use node->next in while condition as the node->next->val is used inside the loop, so each node is compared with the value including the last node.
4. As the first node will not be deleted, we can safely return head.

ListNode* deleteDuplicates(ListNode* head) {
    if (head == NULL) return NULL; // required, as we use node->next as the loop condition
    ListNode *node = head; //previous node
    ListNode *tmp = NULL;
    int v = head->val;
    while(node->next){ //same as current node
        if (node->next->val == v)
        {
            tmp = node->next;
            node->next = tmp->next;
            delete tmp;
        }else{
            node = node->next;
            v = node->val;
        }
    }
    return head;
}

• Remove Linked List Elements Easy

Solution

1. Need to consider the case if the head is changed. Use a pointer prev pointing to the previous node to determine if the current node is in the very beginning.
2. Use tmp variable to point to the node to be deleted.

ListNode* removeElements(ListNode* head, int val) {
    ListNode *prev = NULL;
    ListNode *tmp = NULL;
    ListNode *curr = head;
    while(curr){
        if (curr->val == val)
        {
            tmp = curr;
            if (prev == NULL) // head node
            {
                curr = curr->next;
                head = curr;
            }else{
                prev->next = curr->next;
                curr = curr->next;
            }
            delete tmp;
        }
        else{
            prev = curr;
            curr = curr->next;
        }
    }
    return head;
}