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.
Comments
Post a Comment