Table of contents
1.
Introduction
2.
Example
2.1.
Input
2.2.
Output
3.
Algorithm
3.1.
Example Code
3.2.
Output
4.
Complexities
4.1.
Time complexity
4.2.
Space complexity
5.
Frequently Asked Questions
5.1.
What is the definition of linked lists?
5.2.
What are the drawbacks of using a linked list?
5.3.
Why are linked lists better than arrays in terms of performance?
5.4.
To create a simple linked list, how many pointers are required?
5.5.
Is it possible to store various data types in a linked list?
6.
Conclusion
Last Updated: Mar 27, 2024

Given a Linked List of Line Segments, Remove middle points

Author Manan Singhal
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

A linked set of coordinates is given, with adjacent points forming vertical or horizontal lines. Remove points in the middle of a horizontal or vertical line from the linked list.

Example

Input

(2,3)->(4,3)->(8,3)->(10,3)->(12,3)

Output

The linked list should be changed to the following:
(2,3)->(12,3)

 

There is only one vertical line, so remove all middle points.

Algorithm

  1. With the first and second nodes of the list, respectively, initialize two pointers prev and curr.
  2. Continue iterating through the list until curr is not NULL.
  3. If curr's and prev's x-coordinates are equivalent (i.e., vertical line), then:
    Create a start variable with the value prior, which will be used to indicate the beginning of the section.
    Advance prev and curr by one node
    Run a while loop until curr is not NULL and curr and prev's x-coordinates are equivalent.
    Attach curr after the start and delete the prev node inside the loop.
    In addition, change prev to curr and advance curr by one node.
  4. If curr's and prev's y-coordinates are equal (i.e., horizontal line), then:
    Create a start variable initialized to prev, which will represent the segment's start.
    Advance prev and curr by one node.
    Run a while loop until curr is not NULL and curr and prev's y-coordinates are equivalent.
    Attach curr after the start and delete the prev node inside the loop.
    In addition, change prev to curr and advance curr by one node.
  5. If the two coordinates are not equal, advance prev and curr by one node.

Example Code

/* C++ program to remove middle points from the linked list that represents any line segments */
#include <bits/stdc++.h>

using namespace std;

/* Creating a node with 3 fields including x, y coordinates and a pointer representing next node */
class Node {
	public:
	int x, y;
	Node *next;
};

/* Insert a node at the beginning using this function */
void push(Node ** head_ref, int x,int y)
{
	Node* new_node =new Node();
	new_node->x = x;
	new_node->y = y;
	new_node->next = (*head_ref);
	(*head_ref) = new_node;
}

/* Function to print a linked list */
void printList(Node *head)
{
	Node *temp = head;
	while (temp != NULL)
	{
		cout << "(" << temp->x << "," << temp->y << ")-> ";
		temp = temp->next;
	}
	cout<<endl;

}

/* Function to remove Next from the linked list and link nodes accordingly */
void deleteNode(Node *head, Node *Next)
{
	head->next = Next->next;
	Next->next = NULL;
	free(Next);
}

/* Function deletes middle nodes in a sequence of any line segments represented by a linked list. */
Node* deleteMiddle(Node *head)
{
	/* If only one node or no node then return back */
	if (head == NULL || head->next == NULL || head->next->next == NULL)
		return head;

	Node* Next = head->next;
	Node *NextNext = Next->next ;

	/* Check if this is a horizontal line or vertical line */
	if (head->x == Next->x)
	{
		/* Find middle nodes with same x value, and delete them */
		while (NextNext != NULL && Next->x == NextNext->x)
		{
			deleteNode(head, Next);

			/* Update Next and NextNext for next iteration accordingly */
			Next = NextNext;
			NextNext = NextNext->next;
		}
	}
	else if (head->y==Next->y)
	{
		/* Find middle nodes with same y value, and delete them */
		while (NextNext != NULL && Next->y == NextNext->y)
		{
			deleteNode(head, Next);
			Next = NextNext;
			NextNext = NextNext->next;
		}
	}
	else
	{
		puts("Given linked list is not valid");
		return NULL;
	}

	/* Recursion for next segment */
	deleteMiddle(head->next);

	return head;
}

/* Main Code */
int main()
{
	Node *head = NULL;

	push(&head, 40,5);
	push(&head, 20,5);
	push(&head, 10,5);
	push(&head, 10,8);
	push(&head, 10,10);
	push(&head, 3,10);
	push(&head, 1,10);
	push(&head, 0,10);
	cout << "Given Linked List: \n";
	printList(head);

	if (deleteMiddle(head) != NULL);
	{
		cout << "Modified Linked List: \n";
		printList(head);
	}
	return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Output

Given Linked List:
(0,10)-> (1,10)-> (3,10)-> (10,10)-> (10,8)-> (10,5)-> (20,5)-> (40,5)->
Modified Linked List:
(0,10)-> (10,10)-> (10,5)-> (40,5)->

Complexities

Time complexity

O(n), where n represents nodes in a linked list
Reason: One nested loop is required while traversing the linked list so that the time complexity will be O(n).

Space complexity

O(1),
Reason: No extra space required.

Frequently Asked Questions

What is the definition of linked lists?

It is a data structure for storing a set of things. Linked lists can be used to store many objects of the same kind. Each node has its data as well as the following node's address. It resembles a chain.

What are the drawbacks of using a linked list?

Each node of the linked list points to a pointer, it requires more memory to store the elements than an array. Traversing the nodes of a linked list is quite tough. We won't be able to access any node at random in this case.

Why are linked lists better than arrays in terms of performance?

Arrays allow for random access and use less memory per element, but they are inefficient for insertion/deletion operations and memory allocation. Linked lists are dynamic and have lower insertion/deletion time complexity.

To create a simple linked list, how many pointers are required?

Three types of pointers are often required: A 'head' pointer is used to indicate the beginning of an entry in a list. A 'tail' pointer indicates the last node in a chain. The fact that the last node's following pointer goes to nothing is crucial (NULL).

Is it possible to store various data types in a linked list?

Yes, as long as the list is declared as a List<Object> or List<Serializable>, both string and integer extend.

Conclusion

In this article, we have to remove middle points from the linked list of line segments. We hope that this blog will help you understand the concept of a linked list, and if you would like to learn more about linked lists, check out our other blogs on the linked listsa brief introduction to linked lists, and linked lists in java.

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!

Live masterclass