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.