Linked List Operations and Swap Without Extra Memory
Filed under TCS
Free read 1 of 3Define a Node class with 'val' and 'next' attributes to build the linked list.
The question
Implement a Singly Linked List with basic insertion (at head) and deletion (by value) operations. Additionally, write a function to swap two integer variables without using any temporary or extra memory.
Constraints
- Linked list nodes contain integer values.
- Swap must use bitwise XOR or arithmetic operations.
- Deletion should handle the head node correctly.
Examples
- Input
- List: 1->2->3, Delete: 2; Swap: a=5, b=10
- Output
- List: 1->3; Swap: a=10, b=5
- Why
- The node with value 2 is removed. The integers 5 and 10 are swapped using XOR logic.
Approach
Define a Node class with 'val' and 'next' attributes to build the linked list.
Implement insert by updating the head and delete by traversing with a 'prev' pointer to bypass the target node.
Use the XOR algorithm: a = a ^ b; b = a ^ b; a = a ^ b to swap values without a temp variable.
Solution
O(N) for deletion, O(1) for swap
class Node:
def __init__(self, val):
self.val = val
self.next = None
class LinkedList:
def __init__(self): self.head = None
def insert(self, val):
new_node = Node(val)
new_node.next = self.head
self.head = new_node
def delete(self, val):
curr, prev = self.head, None
while curr:
if curr.val == val:
if prev: prev.next = curr.next
else: self.head = curr.next
return
prev, curr = curr, curr.next
def xor_swap(a, b):
a = a ^ b
b = a ^ b
a = a ^ b
return a, b
Tips
- What they are testing: Test deletion of the head node, the tail node, and a non-existent value.
- Common mistake: In the XOR swap, ensure the two variables are not the same memory address, as 'a ^ a' results in 0.
Related TCS questions
Collected from public candidate posts and coding forums. Updated Nov 2026.