LinkedLists are one of the most common interview topics that we see in interviews.

nth Place from End

This is one of most common interview questions that we've seen in the past from companies like Adobe, AWS, Amazon.

You can find this question pretty much any code practice site like Leetcode, Hackerrank or any other site.

For instance here's a slight variation of the problem on Leetcode: Problem

Strategy:

To find the nth node from the end of a linked list in Python using O(1) space, you can use the two-pointer technique. Here's a step-by-step explanation and implementation:

1. Initialize two pointers, first and second, both pointing to the head of the linked list.

2. Move the first pointer n steps ahead.

3. Move both pointers one step at a time until the first pointer reaches the end of the list.

4. At this point, the second pointer will be pointing to the nth node from the end.

Here's the simplest way to implement it:

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

def find_nth_from_end(head: ListNode, n: int) -> ListNode:
    first = head
    second = head

    # Move the first pointer n steps ahead
    for _ in range(n):
        # If our list is smaller than the n. Return None
        if first is None:
            return None # Out of Bounds
        first = first.next

    # Move both pointers until the first pointer reaches the end
    while first:
        first = first.next
        second = second.next

    return second

Note: There is another way to implement it using Arrays but it'll take up Space Complexity of O(n), which generally is constrained in lot of big interviews.

Find middle of a LinkedList:

This is another common recurring question in LinkedList interviews.

Here's the question on Leetcode: Middle of List

Strategy:

To find the middle of a linked list in Python using O(1) space complexity, you can use the "tortoise and hare" algorithm.

This algorithm involves using two pointers:

• a slow pointer that moves one step at a time

• a fast pointer that moves two steps at a time.

When the fast pointer reaches the end of the list, the slow pointer will be at the middle.

Here's the easiest implementation:

def find_middle(head: ListNode) -> ListNode:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

This algorithm ensures that the space complexity is O(1) since only a constant amount of extra space is used.

Reverse a LinkedList:

Another common question we get asked is to reverse an existing LinkedList using either recursion or using regular way. So in this tutorial we'll cover both:

Iterative Strategy:

• Initialize Three Pointers:

  • prev to None

  • current to the head of the list

  • next to None (will be used to store the next node)

• Iterate Through the List:

  • Update next to current.next

  • Set current.next to prev (this reverses the link)

  • Move prev to current

  • Move current to next

• Set the New Head:

  • After the loop, prev will be the new head of the reversed list.

Perfect and here's the code

def reverse_list(head: ListNode):
    prev = None
    current = head

    while current:
        next = current.next
        current.next = prev
        prev = current
        current = current.next

    # This is the head    
    return prev

Recursion Strategy:

• Base Case:

  • If the node is None or the next node is None, return the node.

• Recursive Step:

  • Reverse the rest of the list from the second node.

  • Set the next node’s next pointer to the current node.

  • Set the current node’s next pointer to None.

• Return the New Head:

  • The new head will be returned from the base case

Perfect and here's the code:

def reverse_list_recursion(head):
    if head is None or head.next is None:
        return head
    rest = reverse_list_recursion(head.next)
    head.next.next = head
    head.next = None
    return rest

These are but some of the concepts we need in LinkedLists. In the remaining series we'll cover easy patterns for:

• Detect a Cycle in a Linked List

• Merge two sorted Linked Lists

• Check if a LinkedList is Palindrome

• Remove duplicates from a sorted LinkedList

• Intersection of two LinkedLists

• Flatten a multilevel doubly LinkedList

• Partion List

• Rotate List

• Add two numbers represented by linked lists

While the code would be important we'll also go through identify common patterns so that we can hack away at any questions the interviewer throws at us.

I hope to hear more from you guys in the Journey and good luck with you #DSA preparations.