26. Linked List : (LL medium-1)

# Note-

Whenever u want new LL , use concept of dummy node.
Start by appending desired nodes onto dummy node & at the end return dummy-->next

----------------------------------------------------------------------------------------------------------------------------

1. Find Middle node-

Brute- time: O(n) 

find length & then traverse LL till (n/2)th position
----------------------------
Optimal time: O(n/2)

Tortoise-Hare approach
use 2 pointers moving at different speed.

Fast pointer moves by 2 steps & Slow pointer move by 1 step.
When fast pointer reaches end of LL, then slow pointer is at middle node.

- write while loop condition as per fast being last or 2nd last node

----------------------------------------------------------------------------------------------------------------------------

2. Delete Middle node-

add a prev pointer in tortoise hare algorithm, to point it to a node just before the middle node, to change links

-------------------------------------------------------------------------------------------------------------------------

3. Del k-th node from end⭐

Let, list has n nodes:

Brute- time: O(n)
k-th node from end=> (n-k+1)th node from start
This can be done as we did : delete a node at a given position in a LL
-----------------
Optimal- time: O(k)

1. Move fast k steps ahead
2. Then move both fast & slow together
3. When fast reaches null, slow will be at node prev to the target node

Logic- 
after (n-k) steps, fast is at last node & slow is at (n-k)th node from the start or (k+1)th from end.

-----------------------------------------------------------------------------------------------------------------------------

4. Reverse LL-

Brute-time: O(n) space: O(n)

traverse the LL & store elements in a stack
Now replace nodes of LL with elements from this stack 

-----------------------------------------------------------------

Optimal-1: (iterative)⭐

we will use 3 pointers- prev, curr, next

1. point current node's next to previous node

2. before this, store pointer to node next to curr, so it do not get lost
3. update prev & current pointer

---------------------------------------------------------------------------

Optimal-2: (recursive)

we will leave reversal of n-1 nodes on recursion and
just reverse 1st node as per other n-1 reversed nodes

----------------------------------------------------------------------------------------------------------------------------

5. Palindrome LL check-

Brute- time: O(n)  space: O(2n)

use stack

---------------------------------------------------------

Optimal-  time: O(n)   space: O(1)

reverse only 2nd half of LL & check Palindrome⭐

1. find middle

2. reverse the 2nd half of linked list (starting from slow-->next)

3. use 2 pointers to check palindrome in both halves

4. again reverse the 2nd half to original configuration
5. return answer
--------------

To initialise slow pointer while reversing 2nd half of LL :

in odd length LL, stop fast pointer at last node.

in even length LL, stop fast pointer at 2nd last node.

-----------------------------------------------------------------------------------------------------------------------------

6. Add 1 to number represented by LL-

Brute- time: O(n)  space: O(n)

use a stack
------------------------------------------------------
Better- time: O(n) space: O(1)

reverse LL & then add 1 from start and update later nodes as per carry
when carry becomes 0 stop
reverse LL again
if carry exists append a new head

---------------------------------------------
Optimal-

instead of reversing
we will use recursion
(go to last node & propagate carry backwards)

-----------------------------------------------------------------------------------------------------------------------------

7. Segregate odd & even numbered nodes

Group all nodes with odd indices together and then even indices together.

-----------------------------------------------
Brute- time: O(n) space: O(n)

we can use a vector to store odd and then even numbered nodes and then over write the actual nodes using this list

-----------------------------------------------------------------

Optimal- time: O(n)  space: O(1)⭐

By changing links

1. Connect all odd nodes
2. Connect all even nodes
3. Connect last odd node to 1st even node
----------------
# remember to save starting node of even list, so we can do step 3 at end.
# Since, even will always be ahead of odd hence we write while loop condition as per even.
------------------

-----------------------------------------------------------------------------------------------------------------------------

8. Sort LL of 0s, 1s, 2s-

Brute- time: O(2n)

count no. of 0s, 1s and 2s and over write the LL
-------------------------------
Optimal- time: O(n) ⭐

Link changing & dummy nodes concept:

- connect all 0s separately
- then all 1s separately
- then all 2s separately
- then connect, (end of 0s to start of 1s) & (end of 1s to start of 2s)

also delete all dummy heads at last to free up space

--------------------------------------------------------------------------------------------------------------------------

9. Detect a loop-

----------------------------------------------------

Brute- time: O(n)  space: O(n)

use hashing

-------------------------------------------------------
Optimal- time: O(n) space: O(1)

using tortoise hare algo

if loop => fast reach a point where it meets slow

else => fast reaches null

Logic: relative speed

-----------------------------------------------------------------------------------------------------------------------------
Note-

To remove a loop in a LL, just point the node (previous to the start of the loop) to NULL

-----------------------------------------------------------------------------------------------------------------------------

10. Length of loop-

Brute- time: O(n) space: O(n)

use hashing
use a counter to count no. of nodes in LL & also use a map to number each node
When u reach a node which is already numbered, then use count & numbering of this node to get total length of loop

------------------------------------------------------------
Optimal- time: O(n) space: O(1)

1. Firstly we set both slow and fast pointers inside the loop at a single node.
2. Now, just use a counter and move fast by 1 step every time, until it meets slow again inside the loop

3. The counter returns total nodes in the loop

----------------------------------------------------------------------------------------------------------------------------

11. Starting point of Loop-⭐

Brute- time: O(n)  space: O(n)

use hashing
----------------------------------
Optimal- time: O(n)  space: O(1)🔥

1. Use detect loop code, to set both pointers to collision point in the loop
2. Reset slow pointer at head of LL & move both pointers by 1 step now
3. Now, the node at which they will collide is start of loop

--------------------------------------------------------------
Intuition-

see apna college mathematical proof
---------------------------------------------------------------------------------------------------------------------------