Singly Linked List
If you have not read about my previous post about LinkedList, navigate straight to https://medium.com/@codedsun/linked-list-simplified-e1d26cceab55
Resuming straight from the previous post. A singly linked list is said to be single because it doesn’t believe into any type of dual relationships :D
It’s a linked list with only one pointer(so called next) which points to the next node in the list.
The main deal here in any problem related to the linkedlist is *How Well you play with the LinkedList pointers* the trick is to get comfortable and getting your hands dirty with them.
Insertion
The basic example of linked list can be represented as
private static class Node {
int data;
Node next;
Node(int e){
data = e;
next = null;
}class LinkedList {
Node head = new Node(1);
head.next = new Node(2); //1-->2
...
}
Deletion/Merging
The deletion are basically of playing with 2 pointers and finding the previous and the next pointers and merging them.
So, just be able to use one more temporary pointers and you are good to go with the deletion problems
Example Pseudocode
To delete the 1st Node
head = head.next
To delete the middle node
Keep track of prev node, next node
Now when next node reaches to the middle node prev.next = next.next
If you have to delete the whole Linked List just, head = null and JVM will handle the rest.
Misc Problems
1.To find the length of linkedlist using recursion
just take a counter with value = 0 which should increase(+1)until head->null and return from the base condition: the value2.Nth node from the end of the linked list
Just use two pointers(slow, fast)..move the fast pointer to n position from the start and
now
move both the pointers until the fast pointer reaches the endreturn the slow pointer which will be pointing to the nth node from the end.
3. To check the loop in the linked list
Can go with a set, hashtable and check for whether this node exist or not.Next, use the flyod cycle detection algorithm
1. now initialize two pointer (slow, fast)
2. move slow pointer by 1 and fast pointer by 2 position
3. Loop until the fast or slow becomes null or when they are at the same locationIf one of them points null-> means that no loop
else they will be at same position
For more such question on linked list
Watch this on Youtube :
Part 1 — https://www.youtube.com/watch?v=VTX-qAKyuYA
Part 2 — https://www.youtube.com/watch?v=XRSYOvnrvsM&t=1234s
Suscribe to the Playlist LinkedList by Suneet Srivastava.
