Data Structure — Linked List| SINGLY LINKED LIST PRACTICE(LeetCode)
A fundamental data structure used to solve many algorithms problems.
What is a linked list?
Linked List is a data structure that consists of a list or set of nodes. Each of these nodes has two elements a value of the data that needs to be stored, it could be a string, integer, or other data structures and a pointer, which points to the next node in the list.
In a singly linked list, every pointer points to the next node. In a doubly-linked list, every node points to two other nodes, the next node and the node that comes before it, the previous node. The representation of these nodes that have properties are called previous or prev, and next for previous and next nodes. A linked list also has a head and a tail. The head is the beginning of a linked list and tail is the final or last node of the list that points to a null value. Linked lists are also called null-terminated, which signifies the end of the list. Here we’ll mainly explore the singly linked list.
Linked Lists are reads from left to right, especially in terms of a singly linked list. The image above is an example singly linked list. Assume, every species represents a node. Australopithecus (node 1) has a pointer that points to the next node on the list, which is homo habilis (node 2). Similarly, homo habilis (node 2) points to homo erectus (node 3), homo erectus (node 3) points to homo neanderthalensis (node 4), homo neanderthalensis (node 4) points to homo sapiens (node 5) and homo sapiens (node 5) points to null. In this case, node 1 is the head of the linked list, which has a value australopithecus; node 5 is the tail that points to a null value, which implies that its the end of the list.
Linked List allows us to easily create, search, insert and remove a value from the beginning, end, and middle of a list. This can be done by simply resetting a few pointers, as you can see in the image below.
This is a great visual of how nodes are removed from a singly linked list. Starting from the head, each node continuously points to the next node, until it finds the nth node. To remove the n node, it simply sets n.prev points to n.next; in this case, 45 points to 87.
LeetCode Question #19 — Remove Nth Node From End of List
Given a linked list, remove the n-th node from the end of the list and return its head.
Input: 1 → 2 → 3 → 4 → 5 n = 2
Output: 1 → 2 → 3 → 5
Note: Given n will always be valid.
Concept: We have a head node of a singly linked list and the nth value. Every node in the list holds an integer value and a pointer that points to the next node on the list. We’d have to remove the nth from the end of the list. In this question, 1 is the head, 5 is the tail, and n = 2, the node that needs to be removed is the node with the value 4. If we count from the end of the list, value 4 is the 2nd node. As you can see in the output, the node with the value 3, points to the node with value 5.
Solution: For this question, I will solve the question by traversing the linked list using two pointers at different indices in the linked list.
- Initialize both pointer1 and pointer2 to the head of the list, with the value 1
- Keep track of a counter variable
- pointer2 will start traversing the linked list before pointer1, pointer2 will iterate n nodes ahead of pointer1 and increment the counter
- Edge cases: if the n is the head node, remove the head node by setting it equal to the next node.
- Next, traverse the linked list using both pointers simultaneously, until pointer2 points to the null value.
- When pointer2 reaches the null value, pointer1 at this point is nth node away from pointer2.
- To remove pointer1, point its next pointer to the next next value (check out the following code for better understanding). In this case, the nth node value is 4, so make the value 3 point to the value 5.
var removeNthFromEnd = function(head, n) {
let counter = 1
let pointer1 = head
let pointer2 = head
while(counter <= n){
pointer2 = pointer2.next
counter++
}
if(pointer2 === null){
head = head.next
return head
}
while(second.next){
pointer2 = pointer2.next
pointer1 = pointer1.next
}
pointer1.next = pointer1.next.next
return head};
This program runs in O(n) time complexity, where n is the length of the linked list. The space complexity is constant time O(1) because I’m not storing anything extra.
