Top 50 LeetCode Linked List Questions for Interview Preparation

When preparing for technical interviews, especially for software engineering and data structure-related roles, it’s crucial to have a solid understanding of linked lists. Linked lists are fundamental data structures, and they frequently appear in coding interviews. In this blog post, we will explore the top 50 LeetCode linked list questions, discuss the concepts behind them, and provide simple examples to help you prepare effectively.

Basics of Linked Lists

A linked list is a data structure composed of nodes, where each node contains two parts:

• Data: The value or payload stored in the node.
• Next: A reference to the next node in the sequence.

Here’s a simple representation of a singly linked list in Python:

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

1. Reverse a Linked List

Problem: Reverse a singly linked list.

Example:
Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 5 -> 4 -> 3 -> 2 -> 1

To solve this problem, you can iterate through the list, reversing the next pointers.

def reverseLinkedList(head):
    prev = None
    current = head

    while current is not None:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    return prev

2. Detect a Cycle in a Linked List

Problem: Determine if a linked list has a cycle.

Example:
Input: 1 -> 2 -> 3 -> 2
Output: True

To solve this problem, you can use the Floyd’s Tortoise and Hare algorithm, also known as the “two-pointer” technique.

def hasCycle(head):
    slow = head
    fast = head

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

3. Merge Two Sorted Lists

Problem: Merge two sorted linked lists into a single sorted list.

Example:
Input: 1 -> 2 -> 4 and 1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4

To solve this problem, you can create a new linked list and compare the values of the nodes from both lists while merging them.

def mergeTwoLists(l1, l2):
    dummy = ListNode(-1)
    current = dummy

    while l1 is not None and l2 is not None:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    if l1 is not None:
        current.next = l1
    else:
        current.next = l2

    return dummy.next

4. Find the Middle of a Linked List

Problem: Find the middle of a linked list.

Example:
Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 3

To find the middle of a linked list, you can use the “slow and fast pointer” technique. Move one pointer at normal speed and the other at double speed; when the fast pointer reaches the end, the slow pointer will be at the middle.

def findMiddle(head):
    slow = head
    fast = head

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

    return slow.val

5. Remove Nth Node From End of List

Problem: Remove the n-th node from the end of a linked list.

Example:
Input: 1 -> 2 -> 3 -> 4 -> 5, n = 2
Output: 1 -> 2 -> 3 -> 5

To solve this problem, you can use two pointers. First, move one pointer n steps ahead. Then, move both pointers together until the first pointer reaches the end.

def removeNthFromEnd(head, n):
    dummy = ListNode(-1)
    dummy.next = head
    first = dummy
    second = dummy

    # Move first n+1 steps ahead
    for i in range(n + 1):
        first = first.next

    # Move first to the end, maintaining the gap
    while first is not None:
        first = first.next
        second = second.next

    # Remove the nth node from the end
    second.next = second.next.next

    return dummy.next

These are just a few examples of 50 LeetCode linked list problems you might encounter in coding interviews. Continuously practicing such problems will not only strengthen your problem-solving skills but also enhance your understanding of linked list operations. To prepare effectively, try to solve these problems on LeetCode and explore more advanced questions in this category.

Stay tuned for Part 2, where we will cover more linked list challenges to help you ace your technical interviews. Happy coding!

Read More –

Navigating Recession: When Will It End and How to Secure a Job – https://kamleshsingad.com/navigating-recession-when-will-it-end-and-how-to-secure-a-job/

Top 20 Object-Oriented Programming (OOP) Questions and Answers for Java Interviews – https://kamleshsingad.com/top-20-object-oriented-programming-oop-questions-and-answers-for-java-interviews/

How to Start Blogging: A Complete Guide with Examples – https://kamleshsingad.com/how-to-start-blogging-a-complete-guide-with-examples/