Introduction to Linked Lists
A linked list is a linear data structure where elements are stored in nodes, and each node points to the next node in the sequence. Unlike arrays, linked lists don't require contiguous memory allocation, making insertions and deletions more efficient.
Key Insight: Linked lists excel at dynamic memory allocation and O(1) insertions/deletions at known positions. However, they sacrifice O(1) random access that arrays provide.
FAANG Interview Prep
Your 12-step learning path • Currently on Step 6
Arrays vs Linked Lists
Comparison Table
| Operation | Array | Linked List |
|---|---|---|
| Access by Index | O(1) | O(n) |
| Insert at Beginning | O(n) | O(1) |
| Insert at End | O(1)* | O(n) / O(1)** |
| Insert in Middle | O(n) | O(n)*** |
| Delete at Beginning | O(n) | O(1) |
| Search | O(n) / O(log n)**** | O(n) |
| Memory | Contiguous | Scattered + Overhead |
* Amortized O(1) for dynamic arrays
** O(1) with tail pointer
*** O(1) once position is found
**** O(log n) if sorted (binary search)
Singly Linked List
In a singly linked list, each node contains data and a pointer to the next node. The last node points to null (or None in Python).
Python
# Singly Linked List - Node Class
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Singly Linked List Implementation
class SinglyLinkedList:
def __init__(self):
self.head = None
self.size = 0
def is_empty(self):
return self.head is None
def __len__(self):
return self.size
# Insert at beginning - O(1)
def insert_at_head(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
self.size += 1
# Insert at end - O(n)
def insert_at_tail(self, data):
new_node = Node(data)
if self.is_empty():
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
self.size += 1
# Insert at position - O(n)
def insert_at_position(self, data, position):
if position < 0 or position > self.size:
raise IndexError("Position out of bounds")
if position == 0:
self.insert_at_head(data)
return
new_node = Node(data)
current = self.head
for _ in range(position - 1):
current = current.next
new_node.next = current.next
current.next = new_node
self.size += 1
# Delete from beginning - O(1)
def delete_from_head(self):
if self.is_empty():
raise IndexError("List is empty")
deleted_data = self.head.data
self.head = self.head.next
self.size -= 1
return deleted_data
# Delete from end - O(n)
def delete_from_tail(self):
if self.is_empty():
raise IndexError("List is empty")
if self.head.next is None:
return self.delete_from_head()
current = self.head
while current.next.next:
current = current.next
deleted_data = current.next.data
current.next = None
self.size -= 1
return deleted_data
# Delete by value - O(n)
def delete_by_value(self, data):
if self.is_empty():
return False
if self.head.data == data:
self.head = self.head.next
self.size -= 1
return True
current = self.head
while current.next:
if current.next.data == data:
current.next = current.next.next
self.size -= 1
return True
current = current.next
return False
# Search - O(n)
def search(self, data):
current = self.head
index = 0
while current:
if current.data == data:
return index
current = current.next
index += 1
return -1
# Get element at index - O(n)
def get(self, index):
if index < 0 or index >= self.size:
raise IndexError("Index out of bounds")
current = self.head
for _ in range(index):
current = current.next
return current.data
# Display list
def display(self):
elements = []
current = self.head
while current:
elements.append(str(current.data))
current = current.next
print(" -> ".join(elements) + " -> None")
# Test Singly Linked List
sll = SinglyLinkedList()
sll.insert_at_tail(1)
sll.insert_at_tail(2)
sll.insert_at_tail(3)
sll.insert_at_head(0)
sll.insert_at_position(1.5, 2)
print("Singly Linked List:")
sll.display() # 0 -> 1 -> 1.5 -> 2 -> 3 -> None
print(f"Size: {len(sll)}")
print(f"Search 2: index {sll.search(2)}")
print(f"Element at index 3: {sll.get(3)}")
sll.delete_from_head()
sll.delete_by_value(1.5)
sll.display() # 1 -> 2 -> 3 -> None
C++
// Singly Linked List Implementation in C++
#include <iostream>
using namespace std;
// Node class
class Node {
public:
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
// Singly Linked List class
class SinglyLinkedList {
private:
Node* head;
int size;
public:
SinglyLinkedList() : head(nullptr), size(0) {}
bool isEmpty() { return head == nullptr; }
int getSize() { return size; }
// Insert at head - O(1)
void insertAtHead(int data) {
Node* newNode = new Node(data);
newNode->next = head;
head = newNode;
size++;
}
// Insert at tail - O(n)
void insertAtTail(int data) {
Node* newNode = new Node(data);
if (isEmpty()) {
head = newNode;
} else {
Node* current = head;
while (current->next) {
current = current->next;
}
current->next = newNode;
}
size++;
}
// Insert at position - O(n)
void insertAtPosition(int data, int position) {
if (position < 0 || position > size) {
throw out_of_range("Position out of bounds");
}
if (position == 0) {
insertAtHead(data);
return;
}
Node* newNode = new Node(data);
Node* current = head;
for (int i = 0; i < position - 1; i++) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
size++;
}
// Delete from head - O(1)
int deleteFromHead() {
if (isEmpty()) throw runtime_error("List is empty");
int deletedData = head->data;
Node* temp = head;
head = head->next;
delete temp;
size--;
return deletedData;
}
// Delete from tail - O(n)
int deleteFromTail() {
if (isEmpty()) throw runtime_error("List is empty");
if (head->next == nullptr) {
return deleteFromHead();
}
Node* current = head;
while (current->next->next) {
current = current->next;
}
int deletedData = current->next->data;
delete current->next;
current->next = nullptr;
size--;
return deletedData;
}
// Search - O(n)
int search(int data) {
Node* current = head;
int index = 0;
while (current) {
if (current->data == data) return index;
current = current->next;
index++;
}
return -1;
}
// Display list
void display() {
Node* current = head;
while (current) {
cout << current->data << " -> ";
current = current->next;
}
cout << "None" << endl;
}
// Destructor
~SinglyLinkedList() {
while (head) {
Node* temp = head;
head = head->next;
delete temp;
}
}
};
int main() {
SinglyLinkedList sll;
sll.insertAtTail(1);
sll.insertAtTail(2);
sll.insertAtTail(3);
sll.insertAtHead(0);
cout << "Singly Linked List: ";
sll.display(); // 0 -> 1 -> 2 -> 3 -> None
cout << "Size: " << sll.getSize() << endl;
cout << "Search 2: index " << sll.search(2) << endl;
sll.deleteFromHead();
sll.display(); // 1 -> 2 -> 3 -> None
return 0;
}
Java
// Singly Linked List Implementation in Java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class SinglyLinkedList {
private Node head;
private int size;
public SinglyLinkedList() {
head = null;
size = 0;
}
public boolean isEmpty() { return head == null; }
public int getSize() { return size; }
// Insert at head - O(1)
public void insertAtHead(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
size++;
}
// Insert at tail - O(n)
public void insertAtTail(int data) {
Node newNode = new Node(data);
if (isEmpty()) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
size++;
}
// Insert at position - O(n)
public void insertAtPosition(int data, int position) {
if (position < 0 || position > size) {
throw new IndexOutOfBoundsException("Position out of bounds");
}
if (position == 0) {
insertAtHead(data);
return;
}
Node newNode = new Node(data);
Node current = head;
for (int i = 0; i < position - 1; i++) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
size++;
}
// Delete from head - O(1)
public int deleteFromHead() {
if (isEmpty()) throw new RuntimeException("List is empty");
int deletedData = head.data;
head = head.next;
size--;
return deletedData;
}
// Delete from tail - O(n)
public int deleteFromTail() {
if (isEmpty()) throw new RuntimeException("List is empty");
if (head.next == null) {
return deleteFromHead();
}
Node current = head;
while (current.next.next != null) {
current = current.next;
}
int deletedData = current.next.data;
current.next = null;
size--;
return deletedData;
}
// Search - O(n)
public int search(int data) {
Node current = head;
int index = 0;
while (current != null) {
if (current.data == data) return index;
current = current.next;
index++;
}
return -1;
}
// Display list
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("None");
}
public static void main(String[] args) {
SinglyLinkedList sll = new SinglyLinkedList();
sll.insertAtTail(1);
sll.insertAtTail(2);
sll.insertAtTail(3);
sll.insertAtHead(0);
System.out.print("Singly Linked List: ");
sll.display(); // 0 -> 1 -> 2 -> 3 -> None
System.out.println("Size: " + sll.getSize());
System.out.println("Search 2: index " + sll.search(2));
sll.deleteFromHead();
sll.display(); // 1 -> 2 -> 3 -> None
}
}
Singly Linked List with Tail Pointer
Python
# Optimized Singly Linked List with Tail Pointer
# Insert at tail becomes O(1)
class SinglyLinkedListWithTail:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def is_empty(self):
return self.head is None
# Insert at tail - O(1) with tail pointer
def insert_at_tail(self, data):
new_node = Node(data)
if self.is_empty():
self.head = self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
self.size += 1
# Insert at head - O(1)
def insert_at_head(self, data):
new_node = Node(data)
if self.is_empty():
self.head = self.tail = new_node
else:
new_node.next = self.head
self.head = new_node
self.size += 1
# Delete from head - O(1)
def delete_from_head(self):
if self.is_empty():
raise IndexError("List is empty")
deleted_data = self.head.data
self.head = self.head.next
if self.head is None:
self.tail = None
self.size -= 1
return deleted_data
# Delete from tail - Still O(n) for singly linked
def delete_from_tail(self):
if self.is_empty():
raise IndexError("List is empty")
if self.head == self.tail:
deleted_data = self.head.data
self.head = self.tail = None
self.size -= 1
return deleted_data
current = self.head
while current.next != self.tail:
current = current.next
deleted_data = self.tail.data
current.next = None
self.tail = current
self.size -= 1
return deleted_data
def display(self):
elements = []
current = self.head
while current:
elements.append(str(current.data))
current = current.next
print(" -> ".join(elements) + " -> None")
# Test
sll_tail = SinglyLinkedListWithTail()
for i in range(5):
sll_tail.insert_at_tail(i)
print("With Tail Pointer:")
sll_tail.display() # 0 -> 1 -> 2 -> 3 -> 4 -> None
C++
// Optimized Singly Linked List with Tail Pointer
// Insert at tail becomes O(1)
#include <iostream>
using namespace std;
class SinglyLinkedListWithTail {
private:
Node* head;
Node* tail;
int size;
public:
SinglyLinkedListWithTail() : head(nullptr), tail(nullptr), size(0) {}
bool isEmpty() { return head == nullptr; }
int getSize() { return size; }
// Insert at tail - O(1) with tail pointer
void insertAtTail(int data) {
Node* newNode = new Node(data);
if (isEmpty()) {
head = tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
size++;
}
// Insert at head - O(1)
void insertAtHead(int data) {
Node* newNode = new Node(data);
if (isEmpty()) {
head = tail = newNode;
} else {
newNode->next = head;
head = newNode;
}
size++;
}
// Delete from head - O(1)
int deleteFromHead() {
if (isEmpty()) throw runtime_error("List is empty");
int deletedData = head->data;
Node* temp = head;
head = head->next;
delete temp;
if (head == nullptr) tail = nullptr;
size--;
return deletedData;
}
// Delete from tail - Still O(n) for singly linked
int deleteFromTail() {
if (isEmpty()) throw runtime_error("List is empty");
if (head == tail) {
int deletedData = head->data;
delete head;
head = tail = nullptr;
size--;
return deletedData;
}
Node* current = head;
while (current->next != tail) {
current = current->next;
}
int deletedData = tail->data;
delete tail;
current->next = nullptr;
tail = current;
size--;
return deletedData;
}
void display() {
Node* current = head;
while (current) {
cout << current->data << " -> ";
current = current->next;
}
cout << "None" << endl;
}
~SinglyLinkedListWithTail() {
while (head) {
Node* temp = head;
head = head->next;
delete temp;
}
}
};
int main() {
SinglyLinkedListWithTail sll;
for (int i = 0; i < 5; i++) {
sll.insertAtTail(i);
}
cout << "With Tail Pointer: ";
sll.display(); // 0 -> 1 -> 2 -> 3 -> 4 -> None
return 0;
}
Java
// Optimized Singly Linked List with Tail Pointer
// Insert at tail becomes O(1)
public class SinglyLinkedListWithTail {
private Node head;
private Node tail;
private int size;
public SinglyLinkedListWithTail() {
head = null;
tail = null;
size = 0;
}
public boolean isEmpty() { return head == null; }
public int getSize() { return size; }
// Insert at tail - O(1) with tail pointer
public void insertAtTail(int data) {
Node newNode = new Node(data);
if (isEmpty()) {
head = tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
size++;
}
// Insert at head - O(1)
public void insertAtHead(int data) {
Node newNode = new Node(data);
if (isEmpty()) {
head = tail = newNode;
} else {
newNode.next = head;
head = newNode;
}
size++;
}
// Delete from head - O(1)
public int deleteFromHead() {
if (isEmpty()) throw new RuntimeException("List is empty");
int deletedData = head.data;
head = head.next;
if (head == null) tail = null;
size--;
return deletedData;
}
// Delete from tail - Still O(n) for singly linked
public int deleteFromTail() {
if (isEmpty()) throw new RuntimeException("List is empty");
if (head == tail) {
int deletedData = head.data;
head = tail = null;
size--;
return deletedData;
}
Node current = head;
while (current.next != tail) {
current = current.next;
}
int deletedData = tail.data;
current.next = null;
tail = current;
size--;
return deletedData;
}
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("None");
}
public static void main(String[] args) {
SinglyLinkedListWithTail sll = new SinglyLinkedListWithTail();
for (int i = 0; i < 5; i++) {
sll.insertAtTail(i);
}
System.out.print("With Tail Pointer: ");
sll.display(); // 0 -> 1 -> 2 -> 3 -> 4 -> None
}
}
Doubly Linked List
In a doubly linked list, each node has pointers to both the next and previous nodes, enabling bidirectional traversal and O(1) deletion when you have a reference to the node.
Python
# Doubly Linked List - Node Class
class DNode:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
# Doubly Linked List Implementation
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def is_empty(self):
return self.head is None
def __len__(self):
return self.size
# Insert at head - O(1)
def insert_at_head(self, data):
new_node = DNode(data)
if self.is_empty():
self.head = self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
self.size += 1
# Insert at tail - O(1)
def insert_at_tail(self, data):
new_node = DNode(data)
if self.is_empty():
self.head = self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
self.size += 1
# Delete node - O(1) if node reference is given
def delete_node(self, node):
if node is None:
return
if node.prev:
node.prev.next = node.next
else:
self.head = node.next
if node.next:
node.next.prev = node.prev
else:
self.tail = node.prev
self.size -= 1
# Delete from head - O(1)
def delete_from_head(self):
if self.is_empty():
raise IndexError("List is empty")
deleted_data = self.head.data
self.delete_node(self.head)
return deleted_data
# Delete from tail - O(1)
def delete_from_tail(self):
if self.is_empty():
raise IndexError("List is empty")
deleted_data = self.tail.data
self.delete_node(self.tail)
return deleted_data
# Display forward
def display_forward(self):
elements = []
current = self.head
while current:
elements.append(str(current.data))
current = current.next
print("None <-> " + " <-> ".join(elements) + " <-> None")
# Test Doubly Linked List
dll = DoublyLinkedList()
for i in range(5):
dll.insert_at_tail(i)
print("Doubly Linked List:")
dll.display_forward() # None <-> 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> None
dll.delete_from_tail()
dll.delete_from_head()
dll.display_forward() # None <-> 1 <-> 2 <-> 3 <-> None
C++
// Doubly Linked List Implementation in C++
#include <iostream>
using namespace std;
// Doubly Linked Node
class DNode {
public:
int data;
DNode* prev;
DNode* next;
DNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};
// Doubly Linked List
class DoublyLinkedList {
private:
DNode* head;
DNode* tail;
int size;
public:
DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
bool isEmpty() { return head == nullptr; }
int getSize() { return size; }
// Insert at head - O(1)
void insertAtHead(int data) {
DNode* newNode = new DNode(data);
if (isEmpty()) {
head = tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
size++;
}
// Insert at tail - O(1)
void insertAtTail(int data) {
DNode* newNode = new DNode(data);
if (isEmpty()) {
head = tail = newNode;
} else {
newNode->prev = tail;
tail->next = newNode;
tail = newNode;
}
size++;
}
// Delete node - O(1) if node reference is given
void deleteNode(DNode* node) {
if (node == nullptr) return;
if (node->prev) {
node->prev->next = node->next;
} else {
head = node->next;
}
if (node->next) {
node->next->prev = node->prev;
} else {
tail = node->prev;
}
delete node;
size--;
}
// Delete from head - O(1)
int deleteFromHead() {
if (isEmpty()) throw runtime_error("List is empty");
int deletedData = head->data;
deleteNode(head);
return deletedData;
}
// Delete from tail - O(1)
int deleteFromTail() {
if (isEmpty()) throw runtime_error("List is empty");
int deletedData = tail->data;
deleteNode(tail);
return deletedData;
}
// Display forward
void displayForward() {
cout << "None <-> ";
DNode* current = head;
while (current) {
cout << current->data << " <-> ";
current = current->next;
}
cout << "None" << endl;
}
// Destructor
~DoublyLinkedList() {
while (head) {
DNode* temp = head;
head = head->next;
delete temp;
}
}
};
int main() {
DoublyLinkedList dll;
for (int i = 0; i < 5; i++) {
dll.insertAtTail(i);
}
cout << "Doubly Linked List: ";
dll.displayForward(); // None <-> 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> None
dll.deleteFromTail();
dll.deleteFromHead();
dll.displayForward(); // None <-> 1 <-> 2 <-> 3 <-> None
return 0;
}
Java
// Doubly Linked List Implementation in Java
class DNode {
int data;
DNode prev;
DNode next;
DNode(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
public class DoublyLinkedList {
private DNode head;
private DNode tail;
private int size;
public DoublyLinkedList() {
head = null;
tail = null;
size = 0;
}
public boolean isEmpty() { return head == null; }
public int getSize() { return size; }
// Insert at head - O(1)
public void insertAtHead(int data) {
DNode newNode = new DNode(data);
if (isEmpty()) {
head = tail = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
size++;
}
// Insert at tail - O(1)
public void insertAtTail(int data) {
DNode newNode = new DNode(data);
if (isEmpty()) {
head = tail = newNode;
} else {
newNode.prev = tail;
tail.next = newNode;
tail = newNode;
}
size++;
}
// Delete node - O(1) if node reference is given
private void deleteNode(DNode node) {
if (node == null) return;
if (node.prev != null) {
node.prev.next = node.next;
} else {
head = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
} else {
tail = node.prev;
}
size--;
}
// Delete from head - O(1)
public int deleteFromHead() {
if (isEmpty()) throw new RuntimeException("List is empty");
int deletedData = head.data;
deleteNode(head);
return deletedData;
}
// Delete from tail - O(1)
public int deleteFromTail() {
if (isEmpty()) throw new RuntimeException("List is empty");
int deletedData = tail.data;
deleteNode(tail);
return deletedData;
}
// Display forward
public void displayForward() {
System.out.print("None <-> ");
DNode current = head;
while (current != null) {
System.out.print(current.data + " <-> ");
current = current.next;
}
System.out.println("None");
}
public static void main(String[] args) {
DoublyLinkedList dll = new DoublyLinkedList();
for (int i = 0; i < 5; i++) {
dll.insertAtTail(i);
}
System.out.print("Doubly Linked List: ");
dll.displayForward(); // None <-> 0 <-> 1 <-> 2 <-> 3 <-> 4 <-> None
dll.deleteFromTail();
dll.deleteFromHead();
dll.displayForward(); // None <-> 1 <-> 2 <-> 3 <-> None
}
}
Circular Linked List
In a circular linked list, the last node points back to the first node, creating a loop. This is useful for applications like round-robin scheduling, circular buffers, and playlists.
Python
# Circular Singly Linked List Implementation
class CircularLinkedList:
def __init__(self):
self.tail = None # Point to last node (easier operations)
self.size = 0
def is_empty(self):
return self.tail is None
# Insert at head - O(1)
def insert_at_head(self, data):
new_node = Node(data)
if self.is_empty():
new_node.next = new_node # Point to itself
self.tail = new_node
else:
new_node.next = self.tail.next # Point to old head
self.tail.next = new_node # Tail points to new head
self.size += 1
# Insert at tail - O(1)
def insert_at_tail(self, data):
self.insert_at_head(data)
self.tail = self.tail.next # Move tail to new node
# Delete from head - O(1)
def delete_from_head(self):
if self.is_empty():
raise IndexError("List is empty")
head = self.tail.next
deleted_data = head.data
if self.tail == head: # Only one node
self.tail = None
else:
self.tail.next = head.next
self.size -= 1
return deleted_data
# Rotate the list (move head to tail)
def rotate(self):
if not self.is_empty():
self.tail = self.tail.next
# Display
def display(self):
if self.is_empty():
print("Empty list")
return
elements = []
current = self.tail.next # Start from head
while True:
elements.append(str(current.data))
current = current.next
if current == self.tail.next:
break
print(" -> ".join(elements) + " -> (back to head)")
# Test Circular Linked List
cll = CircularLinkedList()
for i in range(1, 6):
cll.insert_at_tail(i)
print("Circular Linked List:")
cll.display() # 1 -> 2 -> 3 -> 4 -> 5 -> (back to head)
cll.rotate()
cll.display() # 2 -> 3 -> 4 -> 5 -> 1 -> (back to head)
C++
// Circular Singly Linked List Implementation in C++
#include <iostream>
using namespace std;
class CircularLinkedList {
private:
Node* tail;
int size;
public:
CircularLinkedList() : tail(nullptr), size(0) {}
bool isEmpty() { return tail == nullptr; }
int getSize() { return size; }
// Insert at head - O(1)
void insertAtHead(int data) {
Node* newNode = new Node(data);
if (isEmpty()) {
newNode->next = newNode; // Point to itself
tail = newNode;
} else {
newNode->next = tail->next; // Point to old head
tail->next = newNode; // Tail points to new head
}
size++;
}
// Insert at tail - O(1)
void insertAtTail(int data) {
insertAtHead(data);
tail = tail->next; // Move tail to new node
}
// Delete from head - O(1)
int deleteFromHead() {
if (isEmpty()) throw runtime_error("List is empty");
Node* head = tail->next;
int deletedData = head->data;
if (tail == head) { // Only one node
tail = nullptr;
} else {
tail->next = head->next;
}
delete head;
size--;
return deletedData;
}
// Rotate the list
void rotate() {
if (!isEmpty()) {
tail = tail->next;
}
}
// Display
void display() {
if (isEmpty()) {
cout << "Empty list" << endl;
return;
}
Node* current = tail->next; // Start from head
do {
cout << current->data << " -> ";
current = current->next;
} while (current != tail->next);
cout << "(back to head)" << endl;
}
~CircularLinkedList() {
if (isEmpty()) return;
Node* current = tail->next;
while (current != tail) {
Node* temp = current;
current = current->next;
delete temp;
}
delete tail;
}
};
int main() {
CircularLinkedList cll;
for (int i = 1; i <= 5; i++) {
cll.insertAtTail(i);
}
cout << "Circular Linked List: ";
cll.display(); // 1 -> 2 -> 3 -> 4 -> 5 -> (back to head)
cll.rotate();
cll.display(); // 2 -> 3 -> 4 -> 5 -> 1 -> (back to head)
return 0;
}
Java
// Circular Singly Linked List Implementation in Java
public class CircularLinkedList {
private Node tail;
private int size;
public CircularLinkedList() {
tail = null;
size = 0;
}
public boolean isEmpty() { return tail == null; }
public int getSize() { return size; }
// Insert at head - O(1)
public void insertAtHead(int data) {
Node newNode = new Node(data);
if (isEmpty()) {
newNode.next = newNode; // Point to itself
tail = newNode;
} else {
newNode.next = tail.next; // Point to old head
tail.next = newNode; // Tail points to new head
}
size++;
}
// Insert at tail - O(1)
public void insertAtTail(int data) {
insertAtHead(data);
tail = tail.next; // Move tail to new node
}
// Delete from head - O(1)
public int deleteFromHead() {
if (isEmpty()) throw new RuntimeException("List is empty");
Node head = tail.next;
int deletedData = head.data;
if (tail == head) { // Only one node
tail = null;
} else {
tail.next = head.next;
}
size--;
return deletedData;
}
// Rotate the list
public void rotate() {
if (!isEmpty()) {
tail = tail.next;
}
}
// Display
public void display() {
if (isEmpty()) {
System.out.println("Empty list");
return;
}
Node current = tail.next; // Start from head
do {
System.out.print(current.data + " -> ");
current = current.next;
} while (current != tail.next);
System.out.println("(back to head)");
}
public static void main(String[] args) {
CircularLinkedList cll = new CircularLinkedList();
for (int i = 1; i <= 5; i++) {
cll.insertAtTail(i);
}
System.out.print("Circular Linked List: ");
cll.display(); // 1 -> 2 -> 3 -> 4 -> 5 -> (back to head)
cll.rotate();
cll.display(); // 2 -> 3 -> 4 -> 5 -> 1 -> (back to head)
}
}
Circular Doubly Linked List
Python
# Circular Doubly Linked List Implementation
class CircularDoublyLinkedList:
def __init__(self):
# Use sentinel node for cleaner code
self.sentinel = DNode(None)
self.sentinel.next = self.sentinel
self.sentinel.prev = self.sentinel
self.size = 0
def is_empty(self):
return self.sentinel.next == self.sentinel
# Insert after given node - O(1)
def _insert_after(self, node, data):
new_node = DNode(data)
new_node.prev = node
new_node.next = node.next
node.next.prev = new_node
node.next = new_node
self.size += 1
# Insert at head - O(1)
def insert_at_head(self, data):
self._insert_after(self.sentinel, data)
# Insert at tail - O(1)
def insert_at_tail(self, data):
self._insert_after(self.sentinel.prev, data)
# Delete node - O(1)
def _delete_node(self, node):
if node == self.sentinel:
return None
node.prev.next = node.next
node.next.prev = node.prev
self.size -= 1
return node.data
# Delete from head - O(1)
def delete_from_head(self):
if self.is_empty():
raise IndexError("List is empty")
return self._delete_node(self.sentinel.next)
# Delete from tail - O(1)
def delete_from_tail(self):
if self.is_empty():
raise IndexError("List is empty")
return self._delete_node(self.sentinel.prev)
# Display
def display(self):
elements = []
current = self.sentinel.next
while current != self.sentinel:
elements.append(str(current.data))
current = current.next
print(" <-> ".join(elements) + " <-> (circular)")
# Test
cdll = CircularDoublyLinkedList()
for i in range(1, 6):
cdll.insert_at_tail(i)
cdll.display() # 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> (circular)
C++
// Circular Doubly Linked List with Sentinel Node
#include <iostream>
using namespace std;
class CircularDoublyLinkedList {
private:
DNode* sentinel;
int size;
void insertAfter(DNode* node, int data) {
DNode* newNode = new DNode(data);
newNode->prev = node;
newNode->next = node->next;
node->next->prev = newNode;
node->next = newNode;
size++;
}
int deleteNode(DNode* node) {
if (node == sentinel) return -1;
int data = node->data;
node->prev->next = node->next;
node->next->prev = node->prev;
delete node;
size--;
return data;
}
public:
CircularDoublyLinkedList() {
sentinel = new DNode(0);
sentinel->next = sentinel;
sentinel->prev = sentinel;
size = 0;
}
bool isEmpty() { return sentinel->next == sentinel; }
// Insert at head - O(1)
void insertAtHead(int data) {
insertAfter(sentinel, data);
}
// Insert at tail - O(1)
void insertAtTail(int data) {
insertAfter(sentinel->prev, data);
}
// Delete from head - O(1)
int deleteFromHead() {
if (isEmpty()) throw runtime_error("List is empty");
return deleteNode(sentinel->next);
}
// Delete from tail - O(1)
int deleteFromTail() {
if (isEmpty()) throw runtime_error("List is empty");
return deleteNode(sentinel->prev);
}
void display() {
DNode* current = sentinel->next;
while (current != sentinel) {
cout << current->data << " <-> ";
current = current->next;
}
cout << "(circular)" << endl;
}
~CircularDoublyLinkedList() {
while (!isEmpty()) deleteFromHead();
delete sentinel;
}
};
int main() {
CircularDoublyLinkedList cdll;
for (int i = 1; i <= 5; i++) cdll.insertAtTail(i);
cdll.display(); // 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> (circular)
return 0;
}
Java
// Circular Doubly Linked List with Sentinel Node
public class CircularDoublyLinkedList {
private DNode sentinel;
private int size;
public CircularDoublyLinkedList() {
sentinel = new DNode(0);
sentinel.next = sentinel;
sentinel.prev = sentinel;
size = 0;
}
public boolean isEmpty() { return sentinel.next == sentinel; }
private void insertAfter(DNode node, int data) {
DNode newNode = new DNode(data);
newNode.prev = node;
newNode.next = node.next;
node.next.prev = newNode;
node.next = newNode;
size++;
}
private int deleteNode(DNode node) {
if (node == sentinel) return -1;
int data = node.data;
node.prev.next = node.next;
node.next.prev = node.prev;
size--;
return data;
}
// Insert at head - O(1)
public void insertAtHead(int data) {
insertAfter(sentinel, data);
}
// Insert at tail - O(1)
public void insertAtTail(int data) {
insertAfter(sentinel.prev, data);
}
// Delete from head - O(1)
public int deleteFromHead() {
if (isEmpty()) throw new RuntimeException("List is empty");
return deleteNode(sentinel.next);
}
// Delete from tail - O(1)
public int deleteFromTail() {
if (isEmpty()) throw new RuntimeException("List is empty");
return deleteNode(sentinel.prev);
}
public void display() {
DNode current = sentinel.next;
while (current != sentinel) {
System.out.print(current.data + " <-> ");
current = current.next;
}
System.out.println("(circular)");
}
public static void main(String[] args) {
CircularDoublyLinkedList cdll = new CircularDoublyLinkedList();
for (int i = 1; i <= 5; i++) cdll.insertAtTail(i);
cdll.display(); // 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> (circular)
}
}
Key Techniques
List Reversal
Python
# Reverse Linked List - Three Approaches
# All approaches: Time O(n), Space varies
# 1. Iterative Reversal - Space O(1)
def reverse_iterative(head):
"""Reverse using three pointers"""
prev = None
current = head
while current:
next_node = current.next # Save next
current.next = prev # Reverse link
prev = current # Move prev forward
current = next_node # Move current forward
return prev # New head
# 2. Recursive Reversal - Space O(n) call stack
def reverse_recursive(head):
"""Reverse recursively"""
if not head or not head.next:
return head
new_head = reverse_recursive(head.next)
head.next.next = head
head.next = None
return new_head
# 3. Reverse using Stack - Space O(n)
def reverse_with_stack(head):
"""Reverse using a stack"""
if not head:
return None
stack = []
current = head
while current:
stack.append(current)
current = current.next
new_head = stack.pop()
current = new_head
while stack:
current.next = stack.pop()
current = current.next
current.next = None
return new_head
# Test
original = create_list([1, 2, 3, 4, 5])
display_list(original) # 1 -> 2 -> 3 -> 4 -> 5 -> None
reversed_list = reverse_iterative(original)
display_list(reversed_list) # 5 -> 4 -> 3 -> 2 -> 1 -> None
C++
// Reverse Linked List - Three Approaches
#include <iostream>
#include <stack>
using namespace std;
// 1. Iterative Reversal - O(n) time, O(1) space
ListNode* reverseIterative(ListNode* head) {
ListNode* prev = nullptr;
ListNode* current = head;
while (current) {
ListNode* nextNode = current->next; // Save next
current->next = prev; // Reverse link
prev = current; // Move prev forward
current = nextNode; // Move current forward
}
return prev; // New head
}
// 2. Recursive Reversal - O(n) time, O(n) space (call stack)
ListNode* reverseRecursive(ListNode* head) {
if (!head || !head->next) return head;
ListNode* newHead = reverseRecursive(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
// 3. Reverse using Stack - O(n) time, O(n) space
ListNode* reverseWithStack(ListNode* head) {
if (!head) return nullptr;
stack<ListNode*> stk;
ListNode* current = head;
while (current) {
stk.push(current);
current = current->next;
}
ListNode* newHead = stk.top();
stk.pop();
current = newHead;
while (!stk.empty()) {
current->next = stk.top();
stk.pop();
current = current->next;
}
current->next = nullptr;
return newHead;
}
int main() {
// Create: 1 -> 2 -> 3 -> 4 -> 5
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
head = reverseIterative(head);
// Output: 5 -> 4 -> 3 -> 2 -> 1 -> null
return 0;
}
Java
// Reverse Linked List - Three Approaches
import java.util.Stack;
public class ListReversal {
// 1. Iterative Reversal - O(n) time, O(1) space
public static ListNode reverseIterative(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextNode = current.next; // Save next
current.next = prev; // Reverse link
prev = current; // Move prev forward
current = nextNode; // Move current forward
}
return prev; // New head
}
// 2. Recursive Reversal - O(n) time, O(n) space (call stack)
public static ListNode reverseRecursive(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverseRecursive(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
// 3. Reverse using Stack - O(n) time, O(n) space
public static ListNode reverseWithStack(ListNode head) {
if (head == null) return null;
Stack<ListNode> stack = new Stack<>();
ListNode current = head;
while (current != null) {
stack.push(current);
current = current.next;
}
ListNode newHead = stack.pop();
current = newHead;
while (!stack.isEmpty()) {
current.next = stack.pop();
current = current.next;
}
current.next = null;
return newHead;
}
public static void main(String[] args) {
// Create: 1 -> 2 -> 3 -> 4 -> 5
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
head = reverseIterative(head);
// Output: 5 -> 4 -> 3 -> 2 -> 1 -> null
}
}
Two Pointer Techniques
Python
# Two Pointer Techniques for Linked Lists
# 1. Find Middle Element - Floyd's Tortoise & Hare
def find_middle(head):
"""Find middle node using slow & fast pointers"""
if not head:
return None
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # Middle node
# 2. Find Nth Node from End
def find_nth_from_end(head, n):
"""Find nth node from end using two pointers"""
first = second = head
# Move first pointer n steps ahead
for _ in range(n):
if not first:
return None # n > length
first = first.next
# Move both until first reaches end
while first:
first = first.next
second = second.next
return second
# 3. Check if Palindrome
def is_palindrome(head):
"""Check if linked list is palindrome"""
if not head or not head.next:
return True
# Find middle
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
second_half = reverse_iterative(slow.next)
# Compare both halves
first_half = head
result = True
while second_half:
if first_half.data != second_half.data:
result = False
break
first_half = first_half.next
second_half = second_half.next
return result
# Test
print(f"Middle of [1,2,3,4,5]: {find_middle(create_list([1,2,3,4,5])).data}") # 3
print(f"2nd from end: {find_nth_from_end(create_list([1,2,3,4,5]), 2).data}") # 4
print(f"Is [1,2,3,2,1] palindrome: {is_palindrome(create_list([1,2,3,2,1]))}") # True
C++
// Two Pointer Techniques for Linked Lists
#include <iostream>
using namespace std;
// 1. Find Middle Element - Floyd's Tortoise & Hare
ListNode* findMiddle(ListNode* head) {
if (!head) return nullptr;
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow; // Middle node
}
// 2. Find Nth Node from End
ListNode* findNthFromEnd(ListNode* head, int n) {
ListNode* first = head;
ListNode* second = head;
// Move first pointer n steps ahead
for (int i = 0; i < n; i++) {
if (!first) return nullptr; // n > length
first = first->next;
}
// Move both until first reaches end
while (first) {
first = first->next;
second = second->next;
}
return second;
}
// Helper to reverse list (for palindrome check)
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
while (head) {
ListNode* next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
// 3. Check if Palindrome
bool isPalindrome(ListNode* head) {
if (!head || !head->next) return true;
// Find middle
ListNode* slow = head;
ListNode* fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
// Reverse second half
ListNode* secondHalf = reverseList(slow->next);
// Compare both halves
ListNode* firstHalf = head;
while (secondHalf) {
if (firstHalf->val != secondHalf->val)
return false;
firstHalf = firstHalf->next;
secondHalf = secondHalf->next;
}
return true;
}
int main() {
// Test with 1 -> 2 -> 3 -> 4 -> 5
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
cout << "Middle: " << findMiddle(head)->val << endl; // 3
cout << "2nd from end: " << findNthFromEnd(head, 2)->val << endl; // 4
return 0;
}
Java
// Two Pointer Techniques for Linked Lists
public class TwoPointerTechniques {
// 1. Find Middle Element - Floyd's Tortoise & Hare
public static ListNode findMiddle(ListNode head) {
if (head == null) return null;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // Middle node
}
// 2. Find Nth Node from End
public static ListNode findNthFromEnd(ListNode head, int n) {
ListNode first = head;
ListNode second = head;
// Move first pointer n steps ahead
for (int i = 0; i < n; i++) {
if (first == null) return null; // n > length
first = first.next;
}
// Move both until first reaches end
while (first != null) {
first = first.next;
second = second.next;
}
return second;
}
// Helper to reverse list
private static ListNode reverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
// 3. Check if Palindrome
public static boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
// Find middle
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Reverse second half
ListNode secondHalf = reverseList(slow.next);
// Compare both halves
ListNode firstHalf = head;
while (secondHalf != null) {
if (firstHalf.val != secondHalf.val)
return false;
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return true;
}
public static void main(String[] args) {
// Test with 1 -> 2 -> 3 -> 4 -> 5
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
System.out.println("Middle: " + findMiddle(head).val); // 3
System.out.println("2nd from end: " + findNthFromEnd(head, 2).val); // 4
}
}
Cycle Detection
Python
# Cycle Detection - Floyd's Algorithm
def has_cycle(head):
"""Detect if linked list has a cycle - O(n) time, O(1) space"""
if not head or not head.next:
return False
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
def find_cycle_start(head):
"""Find the starting node of the cycle"""
if not head or not head.next:
return None
slow = fast = head
# Phase 1: Detect cycle
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None # No cycle
# Phase 2: Find cycle start
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow # Cycle start
def get_cycle_length(head):
"""Get the length of the cycle"""
if not head or not head.next:
return 0
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
# Count cycle length
length = 1
current = slow.next
while current != slow:
length += 1
current = current.next
return length
return 0 # No cycle
# Test: Create list with cycle: 1 -> 2 -> 3 -> 4 -> 5 -> 3
nodes = [Node(i) for i in range(1, 6)]
for i in range(4):
nodes[i].next = nodes[i + 1]
nodes[4].next = nodes[2] # 5 -> 3 (cycle)
print(f"Has cycle: {has_cycle(nodes[0])}") # True
print(f"Cycle starts at: {find_cycle_start(nodes[0]).data}") # 3
print(f"Cycle length: {get_cycle_length(nodes[0])}") # 3
C++
// Cycle Detection - Floyd's Algorithm
#include <iostream>
using namespace std;
// Detect if linked list has a cycle - O(n) time, O(1) space
bool hasCycle(ListNode* head) {
if (!head || !head->next) return false;
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
// Find the starting node of the cycle
ListNode* findCycleStart(ListNode* head) {
if (!head || !head->next) return nullptr;
ListNode* slow = head;
ListNode* fast = head;
// Phase 1: Detect cycle
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
if (!fast || !fast->next) return nullptr; // No cycle
// Phase 2: Find cycle start
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow; // Cycle start
}
// Get the length of the cycle
int getCycleLength(ListNode* head) {
if (!head || !head->next) return 0;
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
// Count cycle length
int length = 1;
ListNode* current = slow->next;
while (current != slow) {
length++;
current = current->next;
}
return length;
}
}
return 0; // No cycle
}
int main() {
// Create list with cycle: 1 -> 2 -> 3 -> 4 -> 5 -> 3
ListNode* nodes[5];
for (int i = 0; i < 5; i++) {
nodes[i] = new ListNode(i + 1);
}
for (int i = 0; i < 4; i++) {
nodes[i]->next = nodes[i + 1];
}
nodes[4]->next = nodes[2]; // 5 -> 3 (cycle)
cout << "Has cycle: " << (hasCycle(nodes[0]) ? "true" : "false") << endl;
cout << "Cycle starts at: " << findCycleStart(nodes[0])->val << endl;
cout << "Cycle length: " << getCycleLength(nodes[0]) << endl;
return 0;
}
Java
// Cycle Detection - Floyd's Algorithm
public class CycleDetection {
// Detect if linked list has a cycle - O(n) time, O(1) space
public static boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
// Find the starting node of the cycle
public static ListNode findCycleStart(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head;
ListNode fast = head;
// Phase 1: Detect cycle
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break;
}
if (fast == null || fast.next == null) return null; // No cycle
// Phase 2: Find cycle start
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow; // Cycle start
}
// Get the length of the cycle
public static int getCycleLength(ListNode head) {
if (head == null || head.next == null) return 0;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// Count cycle length
int length = 1;
ListNode current = slow.next;
while (current != slow) {
length++;
current = current.next;
}
return length;
}
}
return 0; // No cycle
}
public static void main(String[] args) {
// Create list with cycle: 1 -> 2 -> 3 -> 4 -> 5 -> 3
ListNode[] nodes = new ListNode[5];
for (int i = 0; i < 5; i++) {
nodes[i] = new ListNode(i + 1);
}
for (int i = 0; i < 4; i++) {
nodes[i].next = nodes[i + 1];
}
nodes[4].next = nodes[2]; // 5 -> 3 (cycle)
System.out.println("Has cycle: " + hasCycle(nodes[0]));
System.out.println("Cycle starts at: " + findCycleStart(nodes[0]).val);
System.out.println("Cycle length: " + getCycleLength(nodes[0]));
}
}
LeetCode Practice Problems
Easy 206. Reverse Linked List
Reverse a singly linked list.
Python
# LeetCode 206 - Reverse Linked List
# Time: O(n), Space: O(1)
def reverseList(head):
prev = None
current = head
while current:
next_temp = current.next
current.next = prev
prev = current
current = next_temp
return prev
# Recursive approach
def reverseListRecursive(head):
if not head or not head.next:
return head
new_head = reverseListRecursive(head.next)
head.next.next = head
head.next = None
return new_head
C++
// LeetCode 206 - Reverse Linked List
// Time: O(n), Space: O(1)
class Solution {
public:
// Iterative approach
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* current = head;
while (current) {
ListNode* nextTemp = current->next;
current->next = prev;
prev = current;
current = nextTemp;
}
return prev;
}
// Recursive approach
ListNode* reverseListRecursive(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode* newHead = reverseListRecursive(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
};
Java
// LeetCode 206 - Reverse Linked List
// Time: O(n), Space: O(1)
class Solution {
// Iterative approach
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
return prev;
}
// Recursive approach
public ListNode reverseListRecursive(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseListRecursive(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
Easy 21. Merge Two Sorted Lists
Merge two sorted linked lists into one sorted list.
Python
# LeetCode 21 - Merge Two Sorted Lists
# Time: O(n + m), Space: O(1)
def mergeTwoLists(list1, list2):
# Create dummy head
dummy = Node(0)
current = dummy
while list1 and list2:
if list1.data <= list2.data:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
# Attach remaining nodes
current.next = list1 if list1 else list2
return dummy.next
C++
// LeetCode 21 - Merge Two Sorted Lists
// Time: O(n + m), Space: O(1)
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode dummy(0);
ListNode* current = &dummy;
while (list1 && list2) {
if (list1->val <= list2->val) {
current->next = list1;
list1 = list1->next;
} else {
current->next = list2;
list2 = list2->next;
}
current = current->next;
}
// Attach remaining nodes
current->next = list1 ? list1 : list2;
return dummy.next;
}
};
Java
// LeetCode 21 - Merge Two Sorted Lists
// Time: O(n + m), Space: O(1)
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
current.next = list1;
list1 = list1.next;
} else {
current.next = list2;
list2 = list2.next;
}
current = current.next;
}
// Attach remaining nodes
current.next = (list1 != null) ? list1 : list2;
return dummy.next;
}
}
Easy 141. Linked List Cycle
Determine if a linked list has a cycle.
Python
# LeetCode 141 - Linked List Cycle
# Time: O(n), Space: O(1)
def hasCycle(head):
if not head or not head.next:
return False
slow = head
fast = head.next
while slow != fast:
if not fast or not fast.next:
return False
slow = slow.next
fast = fast.next.next
return True
C++
// LeetCode 141 - Linked List Cycle
// Time: O(n), Space: O(1)
class Solution {
public:
bool hasCycle(ListNode* head) {
if (!head || !head->next) return false;
ListNode* slow = head;
ListNode* fast = head->next;
while (slow != fast) {
if (!fast || !fast->next) return false;
slow = slow->next;
fast = fast->next->next;
}
return true;
}
};
Java
// LeetCode 141 - Linked List Cycle
// Time: O(n), Space: O(1)
class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) return false;
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
Medium 19. Remove Nth Node From End
Remove the nth node from the end in one pass.
Python
# LeetCode 19 - Remove Nth Node From End
# Time: O(n), Space: O(1)
def removeNthFromEnd(head, n):
dummy = Node(0)
dummy.next = head
first = dummy
second = dummy
# Move first n+1 steps ahead
for _ in range(n + 1):
first = first.next
# Move both until first reaches end
while first:
first = first.next
second = second.next
# Remove nth node
second.next = second.next.next
return dummy.next
C++
// LeetCode 19 - Remove Nth Node From End
// Time: O(n), Space: O(1)
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(0);
dummy.next = head;
ListNode* first = &dummy;
ListNode* second = &dummy;
// Move first n+1 steps ahead
for (int i = 0; i <= n; i++) {
first = first->next;
}
// Move both until first reaches end
while (first) {
first = first->next;
second = second->next;
}
// Remove nth node
ListNode* toDelete = second->next;
second->next = second->next->next;
delete toDelete;
return dummy.next;
}
};
Java
// LeetCode 19 - Remove Nth Node From End
// Time: O(n), Space: O(1)
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
// Move first n+1 steps ahead
for (int i = 0; i <= n; i++) {
first = first.next;
}
// Move both until first reaches end
while (first != null) {
first = first.next;
second = second.next;
}
// Remove nth node
second.next = second.next.next;
return dummy.next;
}
}
Medium 142. Linked List Cycle II
Find the node where the cycle begins.
Python
# LeetCode 142 - Linked List Cycle II
# Time: O(n), Space: O(1)
def detectCycle(head):
if not head or not head.next:
return None
slow = fast = head
# Phase 1: Detect cycle
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
# Phase 2: Find cycle start
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None
C++
// LeetCode 142 - Linked List Cycle II
// Time: O(n), Space: O(1)
class Solution {
public:
ListNode* detectCycle(ListNode* head) {
if (!head || !head->next) return nullptr;
ListNode* slow = head;
ListNode* fast = head;
// Phase 1: Detect cycle
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
// Phase 2: Find cycle start
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return nullptr;
}
};
Java
// LeetCode 142 - Linked List Cycle II
// Time: O(n), Space: O(1)
class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head;
ListNode fast = head;
// Phase 1: Detect cycle
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// Phase 2: Find cycle start
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
Medium 148. Sort List
Sort a linked list in O(n log n) time using constant space.
Python
# LeetCode 148 - Sort List (Merge Sort)
# Time: O(n log n), Space: O(log n) for recursion
def sortList(head):
if not head or not head.next:
return head
# Find middle
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Split list
mid = slow.next
slow.next = None
# Recursively sort both halves
left = sortList(head)
right = sortList(mid)
# Merge sorted halves
return mergeTwoLists(left, right)
C++
// LeetCode 148 - Sort List (Merge Sort)
// Time: O(n log n), Space: O(log n) for recursion
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
// Find middle
ListNode* slow = head;
ListNode* fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
// Split list
ListNode* mid = slow->next;
slow->next = nullptr;
// Recursively sort both halves
ListNode* left = sortList(head);
ListNode* right = sortList(mid);
// Merge sorted halves
return merge(left, right);
}
private:
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (l1 && 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 ? l1 : l2;
return dummy.next;
}
};
Java
// LeetCode 148 - Sort List (Merge Sort)
// Time: O(n log n), Space: O(log n) for recursion
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
// Find middle
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Split list
ListNode mid = slow.next;
slow.next = null;
// Recursively sort both halves
ListNode left = sortList(head);
ListNode right = sortList(mid);
// Merge sorted halves
return merge(left, right);
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
Hard 25. Reverse Nodes in k-Group
Reverse nodes in groups of k. If remaining < k, leave as-is.
Python
# LeetCode 25 - Reverse Nodes in k-Group
# Time: O(n), Space: O(1)
def reverseKGroup(head, k):
# Count total nodes
count = 0
current = head
while current:
count += 1
current = current.next
dummy = Node(0)
dummy.next = head
group_prev = dummy
while count >= k:
# Reverse k nodes
prev = None
current = group_prev.next
for _ in range(k):
next_temp = current.next
current.next = prev
prev = current
current = next_temp
# Connect with previous group
tail = group_prev.next # Tail of reversed group
tail.next = current # Connect to remaining
group_prev.next = prev # Connect prev group to new head
group_prev = tail # Move to next group
count -= k
return dummy.next
C++
// LeetCode 25 - Reverse Nodes in k-Group
// Time: O(n), Space: O(1)
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
// Count total nodes
int count = 0;
ListNode* current = head;
while (current) {
count++;
current = current->next;
}
ListNode dummy(0);
dummy.next = head;
ListNode* groupPrev = &dummy;
while (count >= k) {
// Reverse k nodes
ListNode* prev = nullptr;
current = groupPrev->next;
for (int i = 0; i < k; i++) {
ListNode* nextTemp = current->next;
current->next = prev;
prev = current;
current = nextTemp;
}
// Connect with previous group
ListNode* tail = groupPrev->next;
tail->next = current;
groupPrev->next = prev;
groupPrev = tail;
count -= k;
}
return dummy.next;
}
};
Java
// LeetCode 25 - Reverse Nodes in k-Group
// Time: O(n), Space: O(1)
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// Count total nodes
int count = 0;
ListNode current = head;
while (current != null) {
count++;
current = current.next;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode groupPrev = dummy;
while (count >= k) {
// Reverse k nodes
ListNode prev = null;
current = groupPrev.next;
for (int i = 0; i < k; i++) {
ListNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
// Connect with previous group
ListNode tail = groupPrev.next;
tail.next = current;
groupPrev.next = prev;
groupPrev = tail;
count -= k;
}
return dummy.next;
}
}