Skip to main content

Poridhi: Linked Lists


Linked Lists related problems:

This collection of Python solutions focuses on essential linked list and cache-related problems that frequently appear in coding interviews and real-world system design. It starts with basic operations like merging two sorted linked lists, reversing a list, and finding the middle or removing the nth node from the end. These problems build a solid foundation in manipulating pointers and understanding node traversal. Additionally, the blog includes problems that require smart traversal strategies like cycle detection, detecting intersections, and finding duplicate numbers using Floyd’s Tortoise and Hare algorithm.
More complex scenarios are also covered, such as designing a fully functional custom Linked List and LRU Cache, which help readers understand object-oriented design and memory-efficient structures. Real-world use cases like browser history management and reordering lists for UI rendering are also included to demonstrate how linked lists can be applied in practical applications. Altogether, this blog serves as a comprehensive guide for mastering linked list operations and learning how to optimize memory and data access patterns in systems and applications.

✅ Merge Two Sorted Lists

def mergeTwoLists(l1, l2):
    dummy = curr = ListNode(0)
    while l1 and l2:
        if l1.val < l2.val:
            curr.next, l1 = l1, l1.next
        else:
            curr.next, l2 = l2, l2.next
        curr = curr.next
    curr.next = l1 or l2
    return dummy.next

✅ Design Linked List

class ListNode:
    def __init__(self, val=0, next=None): self.val, self.next = val, next

class MyLinkedList:
    def __init__(self): self.head = None

    def get(self, index):
        curr, i = self.head, 0
        while curr:
            if i == index: return curr.val
            curr, i = curr.next, i + 1
        return -1

    def addAtHead(self, val): self.head = ListNode(val, self.head)

    def addAtTail(self, val):
        if not self.head: self.head = ListNode(val); return
        curr = self.head
        while curr.next: curr = curr.next
        curr.next = ListNode(val)

    def addAtIndex(self, index, val):
        if index == 0: self.addAtHead(val); return
        curr, i = self.head, 0
        while curr:
            if i + 1 == index:
                curr.next = ListNode(val, curr.next)
                return
            curr, i = curr.next, i + 1

    def deleteAtIndex(self, index):
        if index == 0: self.head = self.head.next if self.head else None; return
        curr, i = self.head, 0
        while curr:
            if i + 1 == index and curr.next:
                curr.next = curr.next.next
                return
            curr, i = curr.next, i + 1

✅ Middle of the Linked List

def middleNode(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow

✅ Delete the Middle Node of a Linked List

def deleteMiddle(head):
    if not head or not head.next: return None
    slow, fast, prev = head, head, None
    while fast and fast.next:
        prev, slow, fast = slow, slow.next, fast.next.next
    prev.next = slow.next
    return head

✅ Remove Nth Node From End of List

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    first = second = dummy
    for _ in range(n): first = first.next
    while first.next:
        first, second = first.next, second.next
    second.next = second.next.next
    return dummy.next

✅ Design Browser History (Linked List Solution)

class Node:
    def __init__(self, val):
        self.val, self.prev, self.next = val, None, None

class BrowserHistory:
    def __init__(self, homepage):
        self.curr = Node(homepage)

    def visit(self, url):
        new = Node(url)
        self.curr.next, new.prev = new, self.curr
        self.curr = new

    def back(self, steps):
        while self.curr.prev and steps:
            self.curr, steps = self.curr.prev, steps - 1
        return self.curr.val

    def forward(self, steps):
        while self.curr.next and steps:
            self.curr, steps = self.curr.next, steps - 1
        return self.curr.val

✅ Reverse Linked List

def reverseList(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

✅ Reorder List

def reorderList(head):
    if not head: return
    slow, fast = head, head.next
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    second, slow.next = slow.next, None
    prev = None
    while second:
        second.next, prev, second = prev, second, second.next
    first = head
    while prev:
        tmp1, tmp2 = first.next, prev.next
        first.next = prev
        prev.next = tmp1
        first, prev = tmp1, tmp2

✅ LRU Cache

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.cap = capacity

    def get(self, key):
        if key not in self.cache: return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache: self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap: self.cache.popitem(last=False)

✅ Linked List Cycle

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

✅ Linked List Cycle II

def detectCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow == fast:
            while head != slow:
                head, slow = head.next, slow.next
            return head
    return None

✅ Find the Duplicate Number

def findDuplicate(nums):
    slow = fast = nums[0]
    while True:
        slow, fast = nums[slow], nums[nums[fast]]
        if slow == fast: break
    slow = nums[0]
    while slow != fast:
        slow, fast = nums[slow], nums[fast]
    return slow

✅ Intersection of Two Linked Lists

def getIntersectionNode(headA, headB):
    a, b = headA, headB
    while a != b:
        a = a.next if a else headB
        b = b.next if b else headA
    return a

✅ Add Two Numbers

def addTwoNumbers(l1, l2):
    dummy = curr = ListNode(0)
    carry = 0
    while l1 or l2 or carry:
        v1, v2 = (l1.val if l1 else 0), (l2.val if l2 else 0)
        total = v1 + v2 + carry
        carry, val = divmod(total, 10)
        curr.next = ListNode(val)
        curr = curr.next
        l1, l2 = (l1.next if l1 else None), (l2.next if l2 else None)
    return dummy.next

Comments

Post a Comment

Popular posts from this blog

Poridhi: Stacks & Queues

  Stacks & Queues related problems: This collection of solutions tackles three classic problems often encountered in technical interviews and competitive programming. The Valid Parentheses problem checks whether a string has properly matched and ordered brackets using a stack. The Sliding Window Maximum efficiently finds the maximum value in every window of size k across an array using a deque, a popular sliding window pattern that ensures optimal performance. The Stock Span Problem simulates a real-world stock analysis scenario and calculates the number of consecutive days before today for which the stock price was less than or equal to today's, also utilizing a stack for efficient computation. These problems test understanding of stacks, queues, and sliding window techniques. ✅ Valid Parentheses def isValid ( s: str ) -> bool : stack = [] mapping = { ')' : '(' , '}' : '{' , ']' : '[' } for char in s: ...
Post a Comment
Read more

Data Recovery: DevOps pre-state learning

  Data Backup Data backup is the practice of copying data from a primary to a secondary location, to protect it in case of equipment failure, cyberattack, natural disaster or other data loss events. This can include documents, media files, configuration files, machine images, operating systems, and registry files. Essentially, any data that we want to preserve can be stored as backup data. Data Restore Data restore is the process of copying backup data from secondary storage and restoring it to its original location or a new location. A restore is performed to return data that has been lost, stolen or damaged to its original condition or to move data to a new location. Pilot Light A pilot light approach minimizes the ongoing cost of disaster recovery by minimizing the active resources, and simplifies recovery at the time of a disaster because the core infrastructure requirements are all in place. Warm Standby The warm standby approach involves ensuring that there is a scaled down, ...
Post a Comment
Read more

Poridhi: Basic Programming & Math

Basic Programming and math related problems: Extracting digits means breaking a number like 1234 into [1, 2, 3, 4], often using string conversion or modulo/division. Counting digits involves finding how many digits are in a number using length of a string or repeated division. Reversing an integer flips its digits (e.g., 123 becomes 321), with care for signs and 32-bit limits. A palindrome number reads the same forward and backward, often checked by comparing the original and reversed number. Armstrong numbers are those equal to the sum of their digits each raised to the number of digits, like 153 = 1³ + 5³ + 3³. To find the sum of all divisors of a number, loop through integers and check which divide the number without a remainder. Prime numbers are only divisible by 1 and themselves, and checking up to the square root is efficient. GCD, the greatest common divisor of two numbers, can be found using a simple loop or more efficiently with the Euclidean algorithm, which uses repeated mo...
Post a Comment
Read more