Part1

Reverse a Linked List

❓: Given the head of a singly linked list, write a program to reverse the linked list, and return the head pointer to the reversed list.

# iterative approach
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head
        while curr:
            next_pointer = curr.next
            curr.next = prev
            prev = curr
            curr = next_pointer
        return prev

📘 💻

---

Middle of a Linked List

❓: Given the head of a linked list of integers, determine the middle node of the linked list. However, if the linked list has an even number of nodes, return the second middle node.
🧠:
1. Use slow and fast pointers where fast pointer moves 2 steps and slow pointers moves 1 step at a time
2. When fast pointer is at the end of linked list, slow pointer will be in the middle

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        if fast.next is None:
            return slow
        if fast.next.next is None:
            return slow.next

📘 💻

---

Remove nth node from end

❓: Given a linked list and an integer N, the task is to delete the Nth node from the end of the linked list and print the updated linked list.
🧠:
1. Use 2 pointers slow and fast. Move fast pointer first from head by n steps
2. Now move the slow pointer till fast pointer reaches end.
3. Now the slow pointer's next node needs to be removed
4. Handle the edge case in the start if fast pointer moves beyond linked list

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        fast = head
        for _ in range(n):
            fast = fast.next
        if fast is None:
            return head.next
        slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return head

📘 💻

---

Add 2 Numbers

❓: Given the heads of two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
🧠:
1. Iterate through both linked lists by carrying current remainder
2. Create new node with the remainder and curr sum and return the final linked list

class Solution:
    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        res = curr = None
        remainder = curr_sum = 0
        while l1 or l2:
            curr_sum = (l1.val if l1 else 0) + (l2.val if l2 else 0) + remainder
            remainder = curr_sum // 10

            new_node = ListNode(val=curr_sum % 10)

            if curr is None:
                res = new_node
                curr = new_node
            else:
                curr.next = new_node
                curr = curr.next
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
        if remainder:
            curr.next = ListNode(val=remainder)

        return res

📘 💻

---

Delete the given node

❓: Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list instead, you will be given access to the node to be deleted directly. It is guaranteed that the node to be deleted is not a tail node in the list.
🧠:
Replace the node value with next node value and make next node as next node's next

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next

📘 💻