111 Odd Even Linked List - Group odd and even indexed nodes

 The Odd Even Linked List is a common linked list problem typically found in FAANG-level interviews. It involves reordering a singly linked list such that all nodes at odd indices come before all nodes at even indices, preserving the relative order among odd and even nodes.

Problem Statement

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

Note:

• The node position/index is considered starting from 1 (not 0).

• You must do this in O(1) space and O(n) time complexity.

Intuition

Separate the list into two:

• One list for nodes at odd indices

• One list for nodes at even indices

At the end, link the last node of the odd list to the head of the even list.

Algorithm

1. Edge case: If the list is empty or has one element, return the head.

2. Initialize:

   • odd pointing to the first node,

   • even pointing to the second node,

   • even_head pointing to the head of the even list (used for reconnecting).

3. Iterate while both odd.next and even.next are not null:

   • Link odd.next to odd.next.next

   • Move odd one step

   • Link even.next to even.next.next

   • Move even one step

4. Finally, link the last odd node to even_head.

Time and Space Complexity

• Time: O(n) — Each node is visited once.

• Space: O(1) — Only pointers are used.

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

def create_linked_list(arr):
    head = LinkedListNode(arr[0])

    current = head

    for k in arr[1:]:
        current.next= LinkedListNode(k)
        current = current.next

    return head

def print_linked_list(head):
    res = []
    current = head

    while current:
        res.append(str(current.val))
        current = current.next
    print("=>".join(res))

def odd_even_linkked_list(head):

    if not head or not head.next:
        return head
    
    odd = head
    even = head.next
    even_head = even

    while even and even.next:

        odd.next = even.next
        odd = odd.next

        even.next = odd.next
        even = even.next

    # now we have odd last ref and even_head first ref of even list , lets join together

    odd.next = even_head

    return head

k = create_linked_list([101,102,110,22,44,66,34,98])
print_linked_list(k)

print_linked_list(odd_even_linkked_list(k))

110 Intersection of Two Linked Lists - Return intersecting node

Given: Heads of two singly linked lists.
Return: The node where the two lists intersect (by reference), or None if they don’t intersect.

How It Works:

• Two pointers start at headA and headB.

• When a pointer reaches the end of its list, it switches to the head of the other list.

• If the two lists intersect, they’ll meet at the intersection node.

• If not, both will end up as None at the same time.

Time & Space Complexity:

• Time: O(m + n)

• Space: O(1)

def find_intersecting(heada,headb):

    if not heada or not headb:
        return None

    currentA = heada
    currentB = headb
    while  currentA != currentB:
        if currentA:
            currentA = currentA.next 
        else:
            currentA = headb

        if currentB:
            currentB = currentB.next
        else:
            currentB = heada
    return currentA  # Either the intersecting node or None

How It Works:

• ptrA and ptrB are two pointers, initially starting at headA and headB respectively.

• They traverse the lists node by node.

• When a pointer reaches the end of its list, it is redirected to the start of the other list.

• This ensures that both pointers travel the same total distance, and thus will meet at the intersection point — or both become None if no intersection.

List A:       A1 → A2
                       ↘
                         C1 → C2 → C3
                       ↗
List B: B1 → B2 → B3

109 Find if Its Palindrome Linked List

 

Approach: Fast & Slow Pointer + Reverse Second Half

This is the most optimal solution with:

• Time Complexity: O(n)

• Space Complexity: O(1) (no extra space used)

Steps:

1. Use fast and slow pointers to find the middle.

2. Reverse the second half of the list.

3. Compare both halves node by node.

4. (Optional) Restore the list by reversing the second half again.

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

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head or not head.next:
            return True
        
        # Step 1: Find the middle using fast and slow pointers
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # Step 2: Reverse the second half
        prev = None
        curr = slow
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        
        # Step 3: Compare first half and reversed second half
        first, second = head, prev
        while second:
            if first.val != second.val:
                return False
            first = first.next
            second = second.next
        
        return True

108 Remove N-th Node From End (Two pointers to remove target node)

 

Approach: Two-Pointer (Normal, 2-pass method)

     Idea:

1. First, traverse the entire list to find the length.

2. Then, calculate the (length - n) position from the start.

3. Traverse again to the (length - n - 1)-th node (the node before the one to delete).

4. Delete the N-th node from the end.

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

def removeNthFromEnd(head, n):
    dummy = ListNode(0)
    dummy.next = head

    # Step 1: Find the length
    length = 0
    current = head
    while current:
        length += 1
        current = current.next

    # Step 2: Find (length - n)-th node
    current = dummy
    for _ in range(length - n):
        current = current.next

    # Step 3: Delete the node
    current.next = current.next.next

    return dummy.next

107 while current and while current.next

In linked list problems, both while current and while current.next are common loop conditions, but they serve different purposes depending on what you want to do inside the loop.

Let’s break it down:

while current:

Means: "Keep going as long as the node is not null."

Use it when:
You want to process each node — including the last node.

 Example:

while current:
    print(current.val)
    current = current.next

This loop prints every node’s value, including the last one.

while current.next:

Means: "Keep going as long as the next node exists."

Use it when:
You want to stop at the second-last node — for example, when you need access to the next node or are modifying current.next.

Example:

while current.next:
    current = current.next

This loop stops at the second-to-last node (i.e., it skips the last one) — useful when you want to remove the last node or modify its pointer.

 Use-Case Scenarios and Tips

Common Trick Patterns

1. Skip a Node

while current and current.next:
    if current.next.val == target:
        current.next = current.next.next  # skip it
    else:
        current = current.next

2. Tail Insertion (Traverse to End)

slow = head
fast = head

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

3. Finding Middle Node (Fast/Slow Pointers)

while current.next:
    current = current.next
current.next = new_node

106 Remove Linked List Elements - delete all nodes with a given value

 

Problem Statement

Given the head of a singly linked list and an integer val,
remove all nodes from the list that have val as their value.

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:

Input: head = [], val = 1
Output: []

Example 3:

Input: head = [7,7,7,7], val = 7
Output: []

Constraints:

• The number of nodes in the list is in the range [0, 104].
• 1 <= Node.val <= 50
• 0 <= val <= 50

Approach

We’ll use a dummy node to simplify edge cases (like deleting the head itself).
Then, we’ll iterate through the list and skip any node whose value is equal to val.

Steps

1. Create a dummy node pointing to the head.

2. Initialize a pointer current = dummy.

3. While current.next is not None:

   • If current.next.val == val, remove it:
     current.next = current.next.next

   • Else, move to next node: current = current.next

4. Return dummy.next (new head).

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

def removeElements(head: ListNode, val: int) -> ListNode:
    dummy = ListNode(0)
    dummy.next = head
    current = dummy

    while current.next:
        if current.next.val == val:
            current.next = current.next.next  # skip the node
        else:
            current = current.next

    return dummy.next

105 Linked List Cycle Detect if a cycle exists

 

Problem Statement

Given: The head of a singly linked list.
Goal: Determine whether there is a cycle in the list.

 What is a cycle?

A cycle exists when a node's next pointer refers back to a previous node instead of None.

Approach: Fast and Slow Pointers (Floyd's Algorithm)

Idea:

Use two pointers:

• Slow pointer moves one step at a time.

• Fast pointer moves two steps at a time.

If there is a cycle, the fast pointer will eventually meet the slow pointer.

If there is no cycle, the fast pointer will reach the end (None).

Why it works:

In a cycle, the fast pointer laps around the cycle and will eventually “catch” the slow pointer, similar to two runners on a circular track.

Time	O(n)	In worst case, fast traverses the list once
Space	O(1)	No extra space used

def hasCycle(head: ListNode) -> bool:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next          # 1 step
        fast = fast.next.next     # 2 steps

        if slow == fast:
            return True           # cycle detected

    return False                  # no cycle

Why "eventually"?

Because:

• They do not meet immediately.

• The fast pointer is moving 2 steps at a time, slow is moving 1 step at a time.

• The distance between them changes over time, and they gradually close the gap.

• It may take multiple iterations before they land on the same node.

104 Middle of the Linked List

 Given: A singly linked list.

Goal: Return the middle node of the linked list.
If there are two middle nodes, return the second one.

Example:

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

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


Approach: Two-Pointer (Fast and Slow Pointer)
Idea:
Use two pointers:
Slow pointer: moves one step at a time.
Fast pointer: moves two steps at a time.

How It Works:
When the fast pointer reaches the end of the list, the slow pointer will be at the middle.

Why It Works:
Fast pointer covers double the distance of slow pointer.

So when fast is at the end (or past the end), slow has reached halfway.

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

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

    while fast and fast.next:
        slow = slow.next        # move 1 step
        fast = fast.next.next   # move 2 steps

    return slow

103 Delete Node in a Linked List

Delete Node in a Linked List Delete

Problem Summary

You are given only a reference to a node (not the head) in a singly linked list. The node is not the tail.
You need to delete this node from the list.

What You Cannot Do

• You cannot traverse from the head to find the previous node.

• You do not have access to the previous node, so you can't modify its next pointer.

---

What You Can Do (The Trick )

You copy the value of the next node into the current node, and then delete the next node instead.

ref

class Node:
    def deleteNode(node: ListNode) -> None:
        node.val = node.next.val        # Step 1: Copy value from next node
        node.next = node.next.next      # Step 2: Skip the next node

102 Dummy references (or dummy nodes) in LinkedList

What is a dummy node?

A dummy node is a placeholder node used as the starting point of a new linked list.
It often has a value like -1 or 0, and its main purpose is not for storing data but to help simplify code logic.

---

Why use a dummy node?

• To avoid handling special cases when dealing with the head of the list.

• To build a new list easily without checking if it’s the first node.

• To simplify pointer manipulation (especially useful in deletion or partitioning problems).

• Prevents null pointer exceptions during iteration or insertion.

Common Scenarios / Use Cases

1. Merging Two Sorted Linked Lists

You don’t know which node will be the head of the merged list, so using a dummy node allows you to build the merged list without worrying about head initialization.

dummy = ListNode(-1)
tail = dummy

while l1 and l2:
    if l1.val < l2.val:
        tail.next = l1
        l1 = l1.next
    else:
        tail.next = l2
        l2 = l2.next
    tail = tail.next

tail.next = l1 or l2
return dummy.next

101 Linked List

 

Why Singly Linked Lists Matter

They test:

• Understanding of pointers
• Recursion
• Iteration
• Edge case handling (null nodes, head/tail issues)
• Space and time complexity reasoning

---

Basic Operations on Singly Linked List

1. Insert at Head

Pseudocode:

function insertAtHead(head, value):
    newNode = Node(value)
    newNode.next = head
    return newNode  // new head

 Python Snippet:

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

def insertAtHead(head, value):
    newNode = Node(value)
    newNode.next = head
    return newNode

---

2. Insert at Tail

 Pseudocode:

function insertAtTail(head, value):
    newNode = Node(value)
    if head is null:
        return newNode
    temp = head
    while temp.next != null:
        temp = temp.next
    temp.next = newNode
    return head

 Python Snippet:

def insertAtTail(head, value):
    newNode = Node(value)
    if not head:
        return newNode
    temp = head
    while temp.next:
        temp = temp.next
    temp.next = newNode
    return head

---

3. Delete from Head

 Pseudocode:

function deleteFromHead(head):
    if head is null:
        return null
    return head.next

 Python Snippet:

def deleteFromHead(head):
    if not head:
        return None
    return head.next

---

4. Delete from Tail

 Pseudocode:

function deleteFromTail(head):
    if head is null or head.next is null:
        return null
    temp = head
    while temp.next.next != null:
        temp = temp.next
    temp.next = null
    return head

Python Snippet:

def deleteFromTail(head):
    if not head or not head.next:
        return None
    temp = head
    while temp.next.next:
        temp = temp.next
    temp.next = None
    return head

---

5. Search a Value

 Pseudocode:

function search(head, target):
    temp = head
    while temp != null:
        if temp.val == target:
            return true
        temp = temp.next
    return false

 Python Snippet:

def search(head, target):
    temp = head
    while temp:
        if temp.val == target:
            return True
        temp = temp.next
    return False

---

6. Reverse a Linked List

 Pseudocode:

function reverseList(head):
    prev = null
    curr = head
    while curr != null:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    return prev  // new head

Python Snippet:

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

---

7. Length of Linked List

 Pseudocode:

function getLength(head):
    count = 0
    temp = head
    while temp != null:
        count += 1
        temp = temp.next
    return count

Python Snippet:

def getLength(head):
    count = 0
    temp = head
    while temp:
        count += 1
        temp = temp.next
    return count

---

8. Print Linked List

 Pseudocode:

function printList(head):
    temp = head
    while temp != null:
        print temp.val
        temp = temp.next

 Python Snippet:

def printList(head):
    temp = head
    while temp:
        print(temp.val, end=" -> ")
        temp = temp.next
    print("None")

Beginner-Level Singly Linked List Questions (FAANG-Friendly)

#	Problem Name	Key Concepts	Difficulty	Platform
1	Reverse a Linked List	Iteration, Pointer manipulation	Easy	LeetCode
2	Merge Two Sorted Lists	Dummy node, Two pointers	Easy	LeetCode
3	Remove Duplicates from Sorted List	Edge-case handling	Easy	LeetCode
4	Delete Node in a Linked List	In-place manipulation	Easy	LeetCode
5	Middle of the Linked List	Fast & slow pointers	Easy	LeetCode
6	Linked List Cycle	Floyd’s Cycle Detection	Easy	LeetCode
7	Palindrome Linked List	Fast/slow pointer + reverse second half	Easy-Medium	LeetCode
8	Remove Nth Node From End of List	Two pointers, edge case	Medium	LeetCode
9	Convert Binary Number in a Linked List to Integer	Math, Iteration	Easy	LeetCode
10	Intersection of Two Linked Lists	Length comparison or hashset	Easy	LeetCode