Linked List

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

    206. Reverse Linked List

Explanation :-
We use 3 pointer's prev = previous, curr = current, forw = forward. Where prev will point to the previous pointer, curr will point to the current pointer & forw will point to the next pointer.

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

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

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

Solution :-

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* current = head;
    while (current != nullptr) {
        ListNode* forward = current->next;
        current->next = prev;
        prev = current;

        current = forward;
    }
    return prev;
}

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
}

876. Middle of the Linked List

We will create 2 pointer's fast & slow

• 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 the middle 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;
    }
}