# 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.

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

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;
}
}
}

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

int main() {
// Creating the linked list representing the path
ListNode* head = new ListNode(0, 1);

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.