Topic: Linked Lists in Python – Part 3: Reversing, Detecting Loops, and Middle Node

---

In this part, we’ll explore advanced operations that are frequently asked in coding interviews using singly linked lists.

---

1. Reverse a Linked List (Iterative)

def reverse(self):
    prev = None
    current = self.head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    self.head = prev

• Time Complexity: O(n)
• Space Complexity: O(1)

---

2. Find the Middle of the Linked List

• Use the slow and fast pointer approach.

def find_middle(self):
    slow = fast = self.head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.data if slow else None

---

3. Detect a Loop in the Linked List

• Use Floyd’s Cycle Detection Algorithm (a.k.a. Tortoise and Hare).

def has_loop(self):
    slow = fast = self.head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

---

4. Find the N-th Node from the End

def nth_from_end(self, n):
    first = self.head
    second = self.head

    for _ in range(n):
        if not first:
            return None
        first = first.next

    while first:
        first = first.next
        second = second.next

    return second.data

---

5. Full Example: Testing All Methods

ll = LinkedList()
for value in [10, 20, 30, 40, 50]:
    ll.append(value)

ll.display()
ll.reverse()
ll.display()
print("Middle:", ll.find_middle())
print("Has Loop?", ll.has_loop())
print("3rd from End:", ll.nth_from_end(3))

---

Summary

• Use pointer manipulation for efficient algorithms in linked lists.

• Common techniques:
• Fast/slow pointers
• Reversal by in-place re-linking
• Two-pointer gap approach for nth from end

---

Exercise

• Write a method is_palindrome() that checks if the linked list reads the same forwards and backwards (without converting it to a list or using extra space).

---

#DSA #LinkedList #ReverseList #LoopDetection #TwoPointerTechnique

https://t.iss.one/DataScience4