LinkedList Problems for Beginners DSA || Java and DSA course || Blog 17

-

Linked lists are fundamental data structures in computer science, offering a dynamic and flexible way to organize and manipulate data. In this blog post, we'll dive into several common linked list problems and provide clear, step-by-step solutions using Java. Whether you're preparing for technical interviews or enhancing your data structures skills, understanding how to navigate and manipulate linked lists is crucial.


 

We'll explore five key linked list problems and present efficient Java implementations for each:

 

Question 1:

Problem Statement: Given a singly linked list, remove the nth node from the end of the list and return the resulting linked list. We are provided with the head of the linked list and an integer 'n,' where 1 ≤ n ≤ length of the linked list.

Example 1: Input: [1,2,3,4,5], n = 2 Output: [1,2,3,5] Explanation: In the given linked list, removing the second node from the end results in the modified list [1,2,3,5].

Example 2: Input: [1], n = 1 Output: [] Explanation: Removing the only node from the end results in an empty list.

Approach: To solve this problem, we can use two pointers – one fast and one slow. Initially, both pointers point to the head of the linked list. We move the fast pointer 'n' steps ahead. Then, we move both pointers simultaneously until the fast pointer reaches the end of the list. The slow pointer will be pointing to the node that needs to be removed. We update the pointers accordingly, and the modification is complete.

Code:

class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int length = 0;
ListNode currNode = head;

// Calculate the length of the linked list
while (currNode != null) {
currNode = currNode.next;
length++;
}

int nodeToRemoveIndex = length - n; // Calculate the index of the node to be removed

// Handle the case when n is equal to the length of the list or greater
if (nodeToRemoveIndex < 0) {
return head.next;
}

// Reset currNode to the head
currNode = head;
ListNode prevNode = null;

// Traverse to the node before the one to be removed
for (int i = 0; i < nodeToRemoveIndex; i++) {
prevNode = currNode;
currNode = currNode.next;
}

// Remove the nth node from the end
if (prevNode != null) {
prevNode.next = currNode.next;
} else {
// If prevNode is null, it means we are removing the head of the list
head = head.next;
}

return head; // Return the overall linked list
}
}


 

Question 2:

Problem Statement: Given a sorted singly linked list, our goal is to remove all duplicate elements, leaving only distinct values in the modified linked list. We are provided with the head of the linked list, and the resulting list should maintain its sorted order.

Example 1: Input: [1,1,2] Output: [1,2] Explanation: In the given sorted linked list, duplicate elements are removed, resulting in the modified list [1,2].

Example 2: Input: [1,1,2,3,3] Output: [1,2,3] Explanation: The modified list contains only unique elements in sorted order.

Approach: To solve this problem, we can traverse the linked list and compare each node's value with the next node. If a duplicate is found, we update the next pointer to skip the duplicate node. This way, we can efficiently remove duplicates in a single pass through the linked list while maintaining its sorted order.

Code:

class Solution {
public ListNode deleteDuplicates(ListNode head) {
// Check if the list is empty or has only one element
if (head == null || head.next == null) {
return head; // No duplicates to remove
}

ListNode currNode = head; // Initialize a pointer to the current node

while (currNode != null && currNode.next != null) {
if (currNode.val == currNode.next.val) {
// If the current node's value is the same as the next node's value (duplicate found)
if (currNode.next.next != null) {
// Check if there is another node after the next node
currNode.next = currNode.next.next;
// Skip the duplicate node by updating the next pointer
} else {
currNode.next = null;
// If there are no more nodes after the next node, set the next pointer to null
// to terminate the list (end of duplicates)
}
} else {
currNode = currNode.next;
// If no duplicate is found, move to the next node
}
}

return head; // Return the modified list without duplicates
}
}


 

Question 3:

Problem Statement: Given a singly linked list and a target value, our objective is to remove all nodes containing that value. After the removals, we return the modified linked list. We are provided with the head of the linked list.

Example 1: Input: [1,2,6,3,4,5,6], val = 6 Output: [1,2,3,4,5] Explanation: Nodes with the value 6 are removed from the linked list.

Example 2: Input: [], val = 1 Output: [] Explanation: The linked list is empty, so no removals are performed.

Approach: To solve this problem, we can traverse the linked list, checking each node's value. If the node contains the specified value, we skip that node by updating the next pointer of the previous node. This way, we can efficiently remove all occurrences of the target value in a single pass through the linked list.

Code:

class Solution {
public ListNode removeElements(ListNode head, int val) {
// Check for cases where the head node(s) have the target value
while (head != null && head.val == val) {
// If the value of the current head node matches the target value, move to the next node.
head = head.next;
}

// Create a reference to the current node starting from the head.
ListNode currnode = head;
while (currnode != null && currnode.next != null) {
// Check if the next node's value is equal to the target value.
if (currnode.next.val == val) {
// If the next node has the target value, skip it by updating the "next" reference.
currnode.next = currnode.next.next;
} else {
// If the next node does not have the target value, move to the next node.
currnode = currnode.next;
}
}

// Return the updated head node after removing all instances of the target value.
return head;
}
}


 

Question 4:

Problem Statement: Given a singly linked list, our goal is to reverse the order of its nodes. After the reversal, we return the modified linked list. We are provided with the head of the linked list.

Example 1: Input: [1,2,3,4,5] Output: [5,4,3,2,1] Explanation: The order of nodes is reversed in the modified linked list.

Example 2: Input: [1,2] Output: [2,1] Explanation: The order of nodes is reversed in the modified linked list.

Approach: To reverse a linked list, we can use an iterative approach. We traverse the list, reversing the direction of the pointers as we go along. We maintain three pointers: one for the current node, one for the previous node, and one for the next node. By updating the pointers appropriately, we can reverse the list in a single pass.

Code:

class Solution {
public ListNode reverseList(ListNode head) {
// Initialize two pointers: prev to track the previous node and curr for the current node
ListNode prev = null;
ListNode curr = head;

// Traverse the linked list until the end is reached
while (curr != null) {
// Save the next node in a temporary variable
ListNode nextTemp = curr.next;
// Reverse the link by pointing the current node's next to the previous node
curr.next = prev;
// Move prev and curr pointers one step forward in the list
prev = curr;
curr = nextTemp;
}

// 'prev' now points to the new head of the reversed list
return prev;
}
}

Problem Statement: Given a singly linked list, our objective is to find the middle node(s) of the list. If the list has an odd number of nodes, we return the single middle node. If the list has an even number of nodes, we return the second of the two middle nodes. We are provided with the head of the linked list.

Example 1: Input: [1,2,3,4,5] Output: [3,4,5] Explanation: The middle node of the list is node 3.

Example 2: Input: [1,2,3,4,5,6] Output: [4,5,6] Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Approach: To find the middle node(s) of a linked list, we can use the two-pointer technique. We'll have two pointers, one moving at twice the speed of the other. When the faster pointer reaches the end of the list, the slower pointer will be at the middle. This approach allows us to efficiently find the middle node(s) in a single pass through the linked list.

Code:

class Solution {
public ListNode middleNode(ListNode head) {
// Initialize two pointers, slow and fast, both pointing to the head of the list
ListNode slow = head;
ListNode fast = head;

// Traverse the list with two pointers, with 'fast' moving twice as fast as 'slow'
while (fast != null && fast.next != null) {
slow = slow.next; // Move 'slow' one step
fast = fast.next.next; // Move 'fast' two steps
}

// 'slow' is now at the middle of the list
return slow;
}
}

 

This was all about Linked List Beginner Problems

 __________________________________________________________________________________

Checkout:https://unnatikadamjavadsa.blogspot.com/

Did you like our blog 17??

Tell us in the comment section

Comments

Post a Comment

Popular posts from this blog

Introduction to Java || Java + DSA course || Blog 1

-
Image
What is y our mother tongue? It can be Eng lish, Hindi, Ja pa nes e, R ussian....m any more . There are total 7000 Languages across the world for us to Communicate. But what if we want to talk to a computer? Of course computer doesn't understand English. So what does it understand? Computer understands a simple language called as Binary . Its script contains only 0s and 1s.It seems easy to learn but it isn't. Just to write A in binary is 01000001 . So even if we just want to do a simple thing like adding 2 numbers, it will mostly be hard enough.   Due to these issue, high level languages were invented. What are they? Think of it as a mixture of human language and computer language. Due to these languages humans could command a task to the computer easily. One of the best and easy High level languages is Java Java is the language which can be run on any computer having JDK.(java development kit.We will talk about it in our 2nd blog)  Lets talk about how do we give a comman...
Read more

LinkedList in DSA || Java and DSA course || Blog 16

-
Image
I n simple words, a collection which can contain many objects of the same type, like the ArrayList is a LinkedList. Arraylist uses dynamic array. Lets say we take an array size of 5. we gave input as 1,2,3,4,5. Now, if we gave it one more value, It creates a new arraylist of sizex2 = 5x2 = 10. it copies data from the first arraylist and then appends the new value. if something is removed between the arraylist, every value shifts one by one. Same is with the insert. From this, we can say that arraylist is better for storing values instead of manipulating it. So what is the difference between ArrayList and LinkedList? In this blog we will take a look into Singular LinkedList and code related to it. For a quick overview, contents are, What is LinkedList? Difference between arraylist and linkedlist Creating Node class Add Node at beginning Extend a node Delete first node Delete last node What is LinkedList? LinkedList is nothing but nodes connected to each other. A node is a point ...
Read more