Introduction

LinkedList is one of the most important topic in DSA as it is used in almost every other important topic so it is really important to learn LinkedList from scratch with strong foundation

Why LinkedLists ?

first question that come in our mind why to even learn LinkedLists when we have array and even vectors with dynamic size, so no vectors aren’t sufficient as vectors look like they are but how they work is like

let say you have defined a vector and it got one element means size is 1 now now if you try to insert new element it’s size will be double of current size

means if you have a vector of size 50 and you try to insert 51st element your vector will get 100 size filled so while it is dynamic it wastes lot of memories when working with huge data

While linked list s truly dynamic and we can just increase size of linkedlist decrease it as well

And you know what it is also good for space optimization as array use contagious locations for it’s assignment linkedlist on other hand use non contagious memory

and non contagious memory means randomly located chunks around our primary memory or RAM

so to keep track of it we have to keep details about the next node as if we lost it’s address we will never be able to get it and will become garbage in memory

How LinkedLists ?

class Node {
private:
    int data; // value stored at current node 
    Node* next; // stores address of next node
};

Algorithm

Floyd's Tortoise and Hare algorithm

Problems

Traversal in Linked List [code]

Pattern : Linear traversal :

Intuition :

Linear traversal with a curr ptr until curr is not null

Logic :

• Initialize curr node intially pointing at head

• print value of node where curr node is pointing

• move curr pointer

• repeat till curr is not null

T.C : O(N)

S.C : O(1)

Deletion of the Kth element of LL [code]

Pattern : two pointer approach with one curr and a trailing prev pointer

Intuition :

keep track index or element which is to be deleted and for doing so use linear search with curr and prev pointers

Logic :

• initialize both pointers with pointing to head

• point prev to curr then move curr one step ahead

• if curr is the node to be mark prec→next as curr→next

• disconnect curr from LL and delete it

T.C : O(N)

S.C : O(1)

Insertion at the Kth position of LL [code]

Pattern : traversal with one pointer

Intuition :

Move curr till curr is just before the desired position where we have to insert

Logic :

• move curr till curr→next is pointing toward desired position

• now create newNode with desired value

• insert newNode as newNode→next = curr→next and curr→next = newNode

T.C : O(N)

S.C : O(1)

Add two numbers in LL [code]

» The digits are stored in reverse order with each node storing one digit.

Pattern : two pointer pointing to start of each LL

Intuition :

just move both pointers simultaneously while doing so keep adding there value and don’t forget the carry from previous sum store in the third LL which is supposed to be ans

Logic :

• initialize both pointers pointing to head of both list using curr1,curr2

• calculate the sum by adding value of both curr nodes don’t forget about carry

• if sum is more then 10 take module and store as sum node and update carry after deviding the sum with 10

• keep doing above steps until any one hit NULL

• at end just check if any curr is not NULL then append all the list in current directly

• » Keep in mind you always have to maintain carry

T.C : O(max(N,M)

S.C : O(max(N,M) + 1) » if has carry then may need additional 1

Segregate odd and even nodes in LL [code]

» 1 Indexed list

» Group all the nodes with odd indices followed by all the nodes with even indices and return the reordered list.

Pattern : two pointer : moving with node→next→next each

Intuition :

just keep track of head(given always) it will be head of odd indices element

mark evenHead for head→next if exist it will work as head of all the even indices element

now add other elements of odd and even indices to respective heads

finally point tail of odd indices list to evenHead and return head

Logic :

• as first element is from odd indices element → head of the odd indices elements : head

• as second element is from even indices element → head of the even indices elements : evenHead

• now use two new pointers odd and even pointing directly to the head of respect nodes → head and evenHead

• now move those pointers with node→next = node→next→next

• above step will make sure that for even indices node it says on even indices and on odd if node is at odd index

• » consider proper order if you broke the list you will lose it

T.C : O(N)

S.C : O(1)

Sort a LL of 0's, 1's and 2's [code]

» In case of LL it is always best to reorder the nodes to impress interviewer

Pattern : store required nodes in separate lists

Intuition :

Store all the 0s,1s and 2s in their respective list

Logic :

• create new nodes zeroHead,oneHead,twoHead and respective curr element

• traverse the list from head append various newHead based on the value of the curr<head> node and move curr<zero,one,two> accordingly

• and note that do not make newNodes just mark like currZero→next = curr and then currZero = currZero→next

• Attach tail of LL for zero, twos and ones accordingly and reurn zeroHead

T.C : O(N)

S.C : O(N)

Remove Nth node from the back of the LL [code]

Pattern : two pointer: similar constant window concept

Intuition :

Just like constant sliding window move the window till it’s end reaches the end of LL now delete the element where start of that window is pointing

Logic :

• Move a fast pointer to desired step ahead

• now point a slow pointer to start

• move slow and fast window simultaneously until next of fast pointer is null

• now create a new pointer(temp) and point it to next of slow

• point slow→next to temp→next

• disconnect temp and then delete it

T.C : O(N)

S.C : O(1)

Reverse a LL [code]

Pattern : three pointers : prev, curr,next : game of logic

Intuition :

It is just concept of pointers how to pint them and when to point them to remind order is also important as much as connect between nodes

T.C : O(N)

S.C : O(1)

Add one to a number represented by LL [code]

Pattern : Linear traversal and concept of LL traversal

Intuition :

it’s just when we add 1 we add it to right most digit of number and in LL it means to tail of of LL

Logic :

• Reverse the LL

• Perform addition of one

• Reverse back the LL

• return head

T.C : O(N)

S.C : O(1)

Find Middle of Linked List [code]

Pattern : Fast and slow pointers Floyd's Tortoise and Hare algorithm

Intuition :

if a pointer moves two step at a time it will reach the end of LL while a pointer moving one step at a time will only reach the center

Logic :

• Initialize slow to head and fast to head-next

• move fast like fast = fast→next→next

• simultaneously move slow = slow→next

• keep the loop till fast != NULL && fast->next != NULL

• return slow it will be pointing to middle of the LL

T.C : O(N)

S.C : O(N)

Delete the middle node in LL [code]

Pattern : Fast and slow pointers Floyd's Tortoise and Hare algorithm with a prev pointer

Intuition :

Same as finding middle of LL but do it with a prev pointer point node just before slow pointer

T.C : O(N)

S.C : O(N)

Problem Title [code]

Pattern :

Intuition :

Logic :

T.C : O(N)

S.C : O(N)