Part2

Find the intersection of 2 linked lists

❓: Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
🧠:
1. First find the length difference between 2 linked lists
2. Use 2 pointers cur1, curr2 for 1st and 2nd linked lists respectively
3. If l1 > l2, move curr1 by l1-l2 steps ahead, else do the opposite for curr2
4. Now, curr1 and curr2 are same distance apart from intersection, move them simultaneously to find the junction point

class Solution:
    def getIntersectionNode(
        self, headA: ListNode, headB: ListNode
    ) -> Optional[ListNode]:
        l1 = self.get_length_of_linked_list(headA)
        l2 = self.get_length_of_linked_list(headB)

        curr1 = headA
        curr2 = headB
        if l1 > l2:
            for _ in range(l1 - l2):
                curr1 = curr1.next
        else:
            for _ in range(l2 - l1):
                curr2 = curr2.next
        while curr1 and curr2:
            if curr1 == curr2:
                return curr1
            curr1 = curr1.next
            curr2 = curr2.next
        return None

    def get_length_of_linked_list(self, node: ListNode):
        res = 0
        while node:
            res += 1
            node = node.next
        return res


# TODO need to check optimal approach

📘 💻

---

Detect a cycle in Linked List

🧠:
1. Use slow and fast pointers where fast moves 2 steps at a time and slow moves 1 step at a time
2. If there is a cycle, they will meet each other

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

📘 💻

---

Check for Palindrome

❓: Check if the given Linked List is Palindrome

🧠:
1. Use slow and fast pointers and find the mid of the linked list
2. Reverse the 2nd half of linked list
3. Now travese both nodes and check values are same or not

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        prev = None
        curr = slow
        while curr:
            nextnode = curr.next
            curr.next = prev
            prev = curr
            curr = nextnode
        curr1 = head
        curr2 = prev
        while curr2:
            if curr1.val != curr2.val:
                return False
            curr1 = curr1.next
            curr2 = curr2.next
        return True

📘 💻

---

Starting Point of Loop

❓: Given the head of a linked list that may contain a cycle, return the starting point of that cycle. If there is no cycle in the linked list return null.

🧠:
1. Use slow and fast pointers and and find whether loop is there or not
2. #TODO If yes, now the distance between required node, head and required node and slow is same(Didn't get the approach completely)

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return None
        slow = fast = entry = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                while slow != entry:
                    slow = slow.next
                    entry = entry.next
                return entry
        return None

📘 💻