So, with that let's start.

• Bring up your pen and a fresh new notebook where you have to write all of these thing's which I will teach you right now.

• If you had started learning linked list, then don't quit. Here's why, ask yourself this question when you feel about to quit, "If you had to leave, then why you had start?"

• Look back again at above 2 rule's

Introduction

int arr[] = new int[8]
Array :- [10, 20, 15, 18, 16, 10, 20, 16]

     Advantages                                              DisAdvantages

1. Dynamic Nature                                   1. More memory usage due to address pointer
2. Optimal insertion & deletion                     2. Slow traversal compared to arrays
3. Stack's & queues can be easily implemented       3. No reverse traversal in singly linked list
4. No memory wastage                                4. No random access

Type's of Linked list

1. Singly-linked list: linked list in which each node points to the next node and the last node points to null

2. Doubly-linked list: linked list in which each node has two pointers, p and n, such that p points to the previous node and n points to the next node; the last node's n pointer points to null

3. Circular-linked list: linked list in which each node points to the next node and the last node points back to the first node

4. Circular-Doubly-linked list:

Time Complexity

Access: O(n)
Search: O(n)
Insert: O(1)
Remove: O(1)

Let's see how to create a linked list

--------       --------       --------
|  10  |  -->  |  20  |  -->  |  30  |
--------       --------       --------

Let's see how we traverse in linked list

--------       --------       --------
|  10  |  -->  |  20  |  -->  |  30  |  -->  X
--------       --------       --------
curr^

print:- 10

**************************************************

--------       --------       --------
|  10  |  -->  |  20  |  -->  |  30  |  -->  X
--------       --------       --------
               curr^

print:- 10, 20

**************************************************

--------       --------       --------
|  10  |  -->  |  20  |  -->  |  30  |  -->  X
--------       --------       --------
                              curr^

print:- 10, 20, 30


**************************************************

--------       --------       --------
|  10  |  -->  |  20  |  -->  |  30  |  -->  X
--------       --------       --------
                                           curr^

print & return answer :- 10, 20, 30

Let's see how to insert an element[node] in linked list

Given :-
--------       --------       --------        --------         --------
|  5  |  -->   |  10  |  -->  |  5  |  -->    |  24  |  -->    |  40  |
--------       --------       --------        --------         --------

Insert 30 at 3 index

head˅
--------       --------       --------                  --------         --------
|  5  |  -->   |  10  |  -->  |  5  | --|       |-->    |  24  |  -->    |  40  |
--------       --------       --------  |       |       --------         --------
prev^                         prev^     ˅       |
                                          --------
                                          |  30  |
										  --------
										  toAdd^

Let's delete an element[node] from linked list

Given :-
--------       --------       --------        --------         --------
|  5  |  -->   |  10  |  -->  | 15  |  -->    |  12  |  -->    |  14  |  -->    X
--------       --------       --------        --------         --------

delete 3rd element from linked list

--------       --------       --------        --------         --------
|  5  |  -->   |  10  |  -->  | 15  | |-X-    |  12   | |----> |  14  |  -->    X
--------       --------       --------|       --------  |      --------
                                      |-----------------|

Best Question's to practice

1. Reverse a Linked List

2. Middle of the Linked List

3. Delete Node in a Linked List

4. Merge Two Sorted Linked List

5. Remove duplicates from sorted list

6. Intersection of two linked list

7. Linked List Cycle

8. Palindrome Linked List

9. Swapping Nodes in a Linked List

10. Odd Even Linked List

11. Remove nth node from Linked List

12. Add Two Numbers

13. Swap Nodes in Pairs

14. Split Linked List in Parts

15. Insertion sort on Linked List

16. Merge sort on Linked List

17. Copy list with random pointers

18. Remove zero sum from consecutive nodes from linked list

19. Merge k sorted Linked List

20. Reverse nodes in k group

21. Doubly Linked List

22. Adding a node at the front, at the end, after a node or before a node

23. Deleting a node from the front, from the end, after a node or before a node

24. Circular Doubly Linked List

25. Adding a node at the front, at the end, after a node or before a node

26. Deleting a node from the front, from the end, after a node or before a node

27. LRU Cache

28. LFU Cache

• Prev will hold the previous value becuase, if we break the link. So, we will not lose our linked list

• Similarly forw will point to the next pointer after curr. So, that once link is broken we will not lose our remaining linked list.

• Once curr reaches null our prev will be on our new head. So, we will return our prev as the answer.

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        ListNode forw = null;

        while(curr != null){
            forw = curr.next;
            curr.next = prev;
            prev = curr;
            curr = forw;
        }
        return prev;
    }
}

Fast pointer will move at the speed of 2X

Slow pointer will move at the speed of 1X

If fast pointer reaches null or fast.next is null we will return our slow pointer which mean's our slow pointer is pointing at mid of linked list

class Solution {
    public ListNode middleNode(ListNode head) {
        // Base Condition
        if(head.next == null) return head;

        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

Fast pointer will move at the speed of 2X

Slow pointer will move at the speed of 1X

If fast pointer & slow pointer meet each other we will return true otherwise they there is no cycle we will return false!!

public class Solution {
    public boolean hasCycle(ListNode head) {

        ListNode fast = head;
        ListNode slow = head;

        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;

            if(fast == slow) return true;
        }
        return false;
    }
}

• First we will get the mid so, that we can divide a linked list into two.

• After that, we will reverse the half of the linked list

• Then we have our slow pointer on new head & we will compare the value with old head i.e. head

• We will check these value & move both the pointer's slow & head until slow reaches null.

• If slow reaches null we will return true, otherwise false.

class Solution {
    public ListNode reverse(ListNode head){

        ListNode prev = null;
        ListNode curr = head;
        ListNode forw = null;

        while(curr != null){
            forw = curr.next;
            curr.next = prev;
            prev = curr;
            curr = forw;
        }
        return prev;
    }
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        slow= reverse(slow);
        while(slow != null && (slow.val == head.val)){
            head = head.next;
            slow = slow.next;
        }
        return slow == null;
    }
}

Take 2 pointer's: pointer A walks through List A and List B (since once it hits null, it goes to List B's head).

Pointer B also walks through List B and List A.

Regardless of the length of the two lists, the sum of the lengths are the same (i.e. a+b = b+a), which means that the pointers sync up at the point of intersection.

If the lists never intersected, it's fine too, because they'll sync up at the end of each list, both of which are null.

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;

        while(a != b){
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return b;
    }
}