Hey ππ», I know it's been a while since we embarked on this journey and I want to believe it has been an awesome one! π
Today, we will be solving some of the most common linked list problems on LeetCode. 𧩠The idea is to get you familiar with the concept of linked lists and how to solve problems on them. π‘ The problems we will be tackling will cut across different types of linked lists, with difficulty ranging from easy to hard, all approached step by step. π So, if you've been following this series, then you're good to go! π If not, you might want to check out the previous articles in this series to catch up. π
Course Outline
Introduction
In our last four articles, we have been through the concept of linked list and how to implement them in javascript. We started with the basic singly linked list and then moved on to doubly linked list and circular linked list (Where we also dealt with both singly and doubly circular linked list). In this article, we will be solving some of the most common linked list problems on leetcode from easy to hard across different types of linked list.
Linked List Problem-Solving Approach
When it comes to solving linked list problems, there are certain steps we can follow to ensure we get the correct answer. These steps are:
- Understand the Problem:
- Read the problem statement carefully.
- Identify the input and output.
- Clarify any assumptions or constraints.
- Consider Edge Cases:
- Think about what happens if the linked list is empty.
- Consider the case where the linked list has only one node (the head).
- Plan the Solution:
- Think about the steps needed to solve the problem.
- Consider using pointers or iteration to traverse the linked list (if needed).
- Consider using a dummy node to simplify edge cases (if needed).
- Implement the Solution:
- Write the code to solve the problem.
- Test the Solution:
- Test the solution with different inputs to ensure it works correctly.
- Check for any edge cases that were not considered.
-
Optimize the Solution:
- Consider the time complexity of the solution.
- Look for ways to improve the solution (e.g., using a faster algorithm).
Unfortunately, we won't be dealing with the time complexity of the solution in this article since we are more concerned with the concept and how to solve the problem.
Singly Linked List Problems
Under this section, we will be solving just two of the most common singly linked list problems on leetcode. They are: Reverse Linked List and Merge Two Sorted Lists
Question 1: Reverse Linked List
Given the
headof a singly linked list, reverse the list, and return the reversed list.Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]Example 2: >
> Input: head = [1,2] > Output: [2,1]
Approach
Since we are dealing with a singly linked list, that means there is only a data and a pointer to the next node in a single node. Since we can't traverse the list in reverse, we need to reverse the direction of the list. We can do this by simply changing the direction of the next pointer of each node.
Solution Implementation
/** Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function reverseList(head) {
if (!head) return null;
if (!head.next) return head;
let node = null;
while (head) {
let currentNode = head.next;
head.next = node;
node = head;
head = currentNode;
}
return node;
}
Question 2: Remove Nth Node From End of List
Given the
headof a linked list, remove thenthnode from the end of the list and return its head.Example 1: >
> Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]Example 2: > Input: head = [1], n = 1
Output: []
Approach
- Use two pointers: a fast pointer and a slow pointer.
- Move the fast pointer n nodes ahead.
- Move both pointers until the fast pointer reaches the end.
- The slow pointer will now be at the node before the one to be removed.
- Update the next pointer of the slow pointer to skip the nth node.
- Return the head of the modified list.
Solution Implementation
const removeNthFromEnd = function (head, n) {
// Create a dummy node to handle edge cases (e.g., removing the head)
const newNode = new ListNode(0);
newNode.next = head;
let first = newNode;
let second = newNode;
// Move the first pointer n+1 steps ahead
for (let i = 0; i <= n; i++) {
first = first.next;
}
// Move both pointers until the first pointer reaches the end
while (first !== null) {
first = first.next;
second = second.next;
}
// Remove the nth node by updating the next pointer
second.next = second.next.next;
// Return the head of the modified list (excluding the dummy node)
return newNode.next;
};
Conclusion
In this article, we have solved some of the most common linked list problems on LeetCode π§©. We started with the reverse linked list problem and then moved on to the remove nth node from end of list problem. We have seen how to approach these problems and how to solve them step by step πΆββοΈπ£.
Remember that practice is key to mastering linked list problems πͺ. Here is a linked list problems collection on LeetCode containing about 75 problems ranging from easy to hard π.
Up next... We'll dive into Queue and Stack data structures! πββοΈπ
Stay Updated and Connected
To ensure you don't miss any part of this series and to connect with me for more in-depth
discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data
structures and algorithms, and other exciting tech topics, follow me on:
Stay tuned and happy coding π¨βπ»π
Top comments (0)