Remove Redundant Nodes from LinkedList - C++ Solution

1. Introduction

In this blog post, we'll tackle a problem that involves manipulating a linked list representing a path through a grid. The goal is to remove redundant nodes that do not represent a change in direction, essentially keeping only the endpoints of each vertical and horizontal segment.

Problem

Given a singly-linked list representing a path in a matrix, where each node contains the coordinates of a cell, remove the redundant nodes. A node is redundant if it is neither the starting nor the ending point of a vertical or horizontal path segment.

Example:

Input: (0, 1) → (0, 5) → (0, 8) → (2, 8) → (5, 8) → (7, 8) → (7, 10) → (7, 12) → nullptr

Output: (0, 1) → (0, 8) → (7, 8) → (7, 12) → nullptr

2. Solution Steps

1. Define a structure to represent a node in the linked list, containing the matrix cell's coordinates.

2. Traverse the linked list.

3. At each node, check if it represents a change in direction (either vertical to horizontal or vice versa).

4. If it does not represent a change in direction, remove it from the list.

5. Continue until the end of the list.

3. Code Program

#include <iostream>
using namespace std;

// Define the structure for a ListNode
struct ListNode {
    pair<int, int> coord; // Coordinates in the matrix
    ListNode *next;
    ListNode(int x, int y) : coord(make_pair(x, y)), next(nullptr) {}
};

// Function to remove redundant nodes
ListNode* removeRedundantNodes(ListNode* head) {
    if (!head || !head->next) return head;

    ListNode *current = head;
    while (current->next && current->next->next) {
        // Check if current node, next node and next to next node are either in same row or column
        if ((current->coord.first == current->next->coord.first && current->next->coord.first == current->next->next->coord.first) ||
            (current->coord.second == current->next->coord.second && current->next->coord.second == current->next->next->coord.second)) {
            // Remove the next node
            ListNode *temp = current->next;
            current->next = temp->next;
            delete temp;
        } else {
            current = current->next;
        }
    }
    return head;
}

// Function to print the linked list
void printLinkedList(ListNode* head) {
    while (head) {
        cout << "(" << head->coord.first << ", " << head->coord.second << ") ";
        if (head->next) cout << "→ ";
        head = head->next;
    }
    cout << "nullptr\n";
}

int main() {
    // Creating the linked list representing the path
    ListNode* head = new ListNode(0, 1);
    head->next = new ListNode(0, 5);
    head->next->next = new ListNode(0, 8);
    head->next->next->next = new ListNode(2, 8);
    head->next->next->next->next = new ListNode(5, 8);
    head->next->next->next->next->next = new ListNode(7, 8);
    head->next->next->next->next->next->next = new ListNode(7, 10);
    head->next->next->next->next->next->next->next = new ListNode(7, 12);

    head = removeRedundantNodes(head);
    printLinkedList(head);
    return 0;
}

Output:

(0, 1) → (0, 8) → (7, 8) → (7, 12) → nullptr

Explanation:

The removeRedundantNodes function iterates through the linked list and identifies nodes that do not represent a change in direction. These nodes are then removed from the list, keeping only those nodes that are essential to describe the path. 

The main function demonstrates the process by creating a linked list representing a path, modifying it according to the rules, and then printing the updated list.