Linked List¶
Table of Contents¶
- 203. Remove Linked List Elements (Easy)
- 707. Design Linked List (Medium)
- 206. Reverse Linked List (Easy)
- 237. Delete Node in a Linked List (Medium)
- 2487. Remove Nodes From Linked List (Medium)
- 24. Swap Nodes in Pairs (Medium)
- 19. Remove Nth Node From End of List (Medium)
- 160. Intersection of Two Linked Lists (Easy)
- 141. Linked List Cycle (Easy)
- 142. Linked List Cycle II (Medium)
- 2816. Double a Number Represented as a Linked List (Medium)
- 2. Add Two Numbers (Medium)
203. Remove Linked List Elements¶
"""
- Remove all elements from a linked list of integers that have value `val`.
"""
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
# Iterative
def removeElements(head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy = ListNode(0)
dummy.next = head
cur = dummy
while cur.next:
if cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.next
# |-------------|-----------------|--------------|
# | Approach | Time | Space |
# |-------------|-----------------|--------------|
# | Iterative | O(N) | O(1) |
# |-------------|-----------------|--------------|
def test_removeElements():
# Test case 1: Remove elements from middle and end
nums = [1, 2, 6, 3, 4, 5, 6]
val = 6
ll = LinkedList(nums)
assert ll.to_array() == [1, 2, 6, 3, 4, 5, 6]
result = removeElements(ll.head, val)
ll_result = LinkedList(result)
assert ll_result.to_array() == [1, 2, 3, 4, 5]
# Test case 2: Remove all elements
ll2 = LinkedList([7, 7, 7, 7])
result2 = removeElements(ll2.head, 7)
assert result2 is None
# Test case 3: Remove elements from beginning
ll3 = LinkedList([1, 1, 2, 3, 4])
result3 = removeElements(ll3.head, 1)
ll_result3 = LinkedList(result3)
assert ll_result3.to_array() == [2, 3, 4]
# Test case 4: No elements to remove
ll4 = LinkedList([1, 2, 3, 4])
result4 = removeElements(ll4.head, 5)
ll_result4 = LinkedList(result4)
assert ll_result4.to_array() == [1, 2, 3, 4]
707. Design Linked List¶
"""
- Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
"""
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class MyLinkedList:
def __init__(self):
self.dummy = ListNode()
self.size = 0
def get(self, index: int) -> int:
if index < 0 or index >= self.size:
return -1
current = self.dummy.next
for _ in range(index):
current = current.next
return current.val
def addAtHead(self, val: int) -> None:
self.dummy.next = ListNode(val, self.dummy.next)
self.size += 1
def addAtTail(self, val: int) -> None:
current = self.dummy
while current.next:
current = current.next
current.next = ListNode(val)
self.size += 1
def addAtIndex(self, index: int, val: int) -> None:
if index < 0 or index > self.size:
return
current = self.dummy
for i in range(index):
current = current.next
current.next = ListNode(val, current.next)
self.size += 1
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
current = self.dummy
for i in range(index):
current = current.next
current.next = current.next.next
self.size -= 1
ll = MyLinkedList()
ll.addAtHead(1)
ll.addAtTail(3)
ll.addAtIndex(1, 2) # 1 -> 2 -> 3
print(ll.get(1)) # 2
206. Reverse Linked List¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
def reverse_list_iterative(head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
prev = None
while cur:
temp = cur.next
cur.next = prev
prev = cur
cur = temp
return prev
def reverse_list_recursive(head: Optional[ListNode]) -> Optional[ListNode]:
def reverse(cur, prev):
if not cur:
return prev
temp = cur.next
cur.next = prev
return reverse(temp, cur)
return reverse(head, None)
def test_reverse_list():
ll = LinkedList([1, 2, 3, 4, 5])
ll.head = reverse_list_iterative(ll.head)
assert ll.to_array() == [5, 4, 3, 2, 1]
ll = LinkedList([1, 2, 3, 4, 5])
ll.head = reverse_list_recursive(ll.head)
assert ll.to_array() == [5, 4, 3, 2, 1]
237. Delete Node in a Linked List¶
"""
- Delete a node in a singly linked list. You are given only the node to be deleted.
"""
from leetpattern.utils import LinkedList, ListNode
def deleteNode(node: ListNode) -> None:
node.val = node.next.val
node.next = node.next.next
def test_deleteNode():
# Test case 1: Delete middle node
ll = LinkedList([4, 5, 1, 9])
assert ll.to_array() == [4, 5, 1, 9]
node = ll.head.next # node with value 5
deleteNode(node)
assert ll.to_array() == [4, 1, 9]
# Test case 2: Delete another middle node
ll2 = LinkedList([4, 5, 1, 9])
node2 = ll2.head.next.next # node with value 1
deleteNode(node2)
assert ll2.to_array() == [4, 5, 9]
2487. Remove Nodes From Linked List¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
def remove_nodes_recursive(head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return None
head.next = remove_nodes_recursive(head.next)
if head.next and head.val < head.next.val:
return head.next
return head
def remove_nodes_iterative(head: Optional[ListNode]) -> Optional[ListNode]:
stack = []
cur = head
while cur:
while stack and cur.val > stack[-1].val:
stack.pop()
stack.append(cur)
cur = cur.next
dummy = ListNode()
cur = dummy
for node in stack:
cur.next = node
cur = cur.next
return dummy.next
def test_remove_nodes() -> None:
ll = LinkedList([5, 2, 13, 3, 8])
ll = LinkedList(remove_nodes_recursive(ll.head))
assert ll.to_array() == [13, 8]
ll = LinkedList([5, 2, 13, 3, 8])
ll = LinkedList(remove_nodes_iterative(ll.head))
assert ll.to_array() == [13, 8]
24. Swap Nodes in Pairs¶
"""
- Given a linked list, swap every two adjacent nodes and return its head.
"""
from typing import Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
def swap_pairs(head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0, head)
n0 = dummy
n1 = dummy.next
while n1 and n1.next:
n2 = n1.next
n3 = n2.next
n0.next = n2
n2.next = n1
n1.next = n3
n0 = n1
n1 = n3
return dummy.next
def test_swap_pairs():
head = list_from_array([1, 2, 3, 4, 5])
assert list_to_array(swap_pairs(head)) == [2, 1, 4, 3, 5]
19. Remove Nth Node From End of List¶
"""
- Given the `head` of a linked list, remove the `n-th` node from the end of the list and return its head.
"""
from typing import Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
# Linked List
def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
fast, slow = dummy, dummy
for _ in range(n):
fast = fast.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
def test_removeNthFromEnd() -> None:
head = list_from_array([1, 2, 3, 4, 5])
assert (list_to_array(removeNthFromEnd(head, 2))) == [1, 2, 3, 5]
160. Intersection of Two Linked Lists¶
"""
- Find the node at which the intersection of two singly linked lists begins.
"""
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
# Hash Set
def getIntersectionNodeHash(headA: ListNode, headB: ListNode) -> Optional[ListNode]:
if not headA or not headB:
return None
visited = set()
cur = headA
while cur:
visited.add(cur)
cur = cur.next
cur = headB
while cur:
if cur in visited:
return cur
cur = cur.next
return None
# Two Pointers
def getIntersectionNodeTP(headA: ListNode, headB: ListNode) -> Optional[ListNode]:
if not headA or not headB:
return None
a, b = headA, headB
while a != b:
a = a.next if a else headB
b = b.next if b else headA
return a
def test_intersection():
# Test case 1: Lists with intersection
llA = LinkedList([4, 1, 8, 4, 5])
llB = LinkedList([5, 6, 1])
# Create intersection at node with value 8
nodeA = llA.head
while nodeA and nodeA.val != 8:
nodeA = nodeA.next
# Connect listB to the intersection point
llB.head.next.next.next = nodeA
assert llA.to_array() == [4, 1, 8, 4, 5]
intersection_hash = getIntersectionNodeHash(llA.head, llB.head)
intersection_tp = getIntersectionNodeTP(llA.head, llB.head)
assert intersection_hash is not None
assert intersection_tp is not None
assert intersection_hash.val == 8
assert intersection_tp.val == 8
assert intersection_hash == intersection_tp
# Test case 2: Lists without intersection
llC = LinkedList([2, 6, 4])
llD = LinkedList([1, 5])
intersection_hash = getIntersectionNodeHash(llC.head, llD.head)
intersection_tp = getIntersectionNodeTP(llC.head, llD.head)
assert intersection_hash is None
assert intersection_tp is None
141. Linked List Cycle¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
def has_cycle(head: Optional[ListNode]) -> bool:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
def test_has_cycle():
ll = LinkedList([3, 2, 0, -4])
ll.make_cycle(pos=1)
assert has_cycle(ll.head)
ll = LinkedList([1, 2])
ll.make_cycle(pos=0)
assert has_cycle(ll.head)
ll = LinkedList([1, 2, 3, 4, 5])
assert not has_cycle(ll.head)
#include <cassert>
#include <iostream>
#include "include/lists.hpp"
using namespace std;
class Solution {
public:
bool has_cycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (fast == slow) return true;
}
return false;
}
};
int main() {
Solution solution;
ListNode* head = LinkedList::build({3, 2, 0, -4});
// create cycle
head = LinkedList::make_cycle(head, 1);
assert(solution.has_cycle(head) == true);
// no cycle
ListNode* head2 = LinkedList::build({1, 2});
assert(solution.has_cycle(head2) == false);
// no cycle
ListNode* head3 = LinkedList::build({1});
assert(solution.has_cycle(head3) == false);
return 0;
}
142. Linked List Cycle II¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
def detectCycle(head: Optional[ListNode]) -> Optional[ListNode]:
slow, fast = head, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if slow == fast:
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None
def test_detectCycle():
l1 = LinkedList([3, 2, 0, -4])
l1.make_cycle(1)
assert detectCycle(l1.head).val == 2
l2 = LinkedList([3, 2, 0, -4])
assert not detectCycle(l2.head)
#include <cassert>
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* detectCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (fast == slow) {
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return nullptr;
}
};
int main() {
Solution sol;
ListNode* head = new ListNode(3);
head->next = new ListNode(2);
head->next->next = new ListNode(0);
head->next->next->next = new ListNode(-4);
head->next->next->next->next = head->next; // Create a cycle
assert(sol.detectCycle(head) == head->next);
ListNode* head2 = new ListNode(1);
head2->next = new ListNode(2);
head2->next->next = head2; // Create a cycle
assert(sol.detectCycle(head2) == head2);
ListNode* head3 = new ListNode(1);
assert(sol.detectCycle(head3) == nullptr);
ListNode* head4 = nullptr;
assert(sol.detectCycle(head4) == nullptr);
return 0;
}
2816. Double a Number Represented as a Linked List¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
def doubleIt(head: Optional[ListNode]) -> Optional[ListNode]:
def twice(node):
if not node:
return 0
doubled = node.val * 2 + twice(node.next)
node.val = doubled % 10
return doubled // 10
carry = twice(head)
if carry:
head = ListNode(val=carry, next=head)
return head
def test_doubleIt() -> None:
ll = LinkedList([9, 9, 9])
ll = LinkedList(doubleIt(ll.head))
assert ll.to_array() == [1, 9, 9, 8]
2. Add Two Numbers¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
def add_two_numbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
"""Add two numbers represented by linked lists."""
dummy = ListNode()
cur = dummy
carry = 0
while l1 or l2:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
carry, val = divmod(v1 + v2 + carry, 10)
cur.next = ListNode(val)
cur = cur.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
if carry:
cur.next = ListNode(val=carry)
return dummy.next
def test_add_two_numbers():
l1 = LinkedList([2, 4, 3]).head
l2 = LinkedList([5, 6, 4]).head
added = add_two_numbers(l1, l2)
assert LinkedList(added).to_array() == [7, 0, 8]
#include <cassert>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy;
ListNode* cur = &dummy;
int carry = 0;
while (l1 || l2 || carry) {
if (l1) {
carry += l1->val;
l1 = l1->next;
}
if (l2) {
carry += l2->val;
l2 = l2->next;
}
cur->next = new ListNode(carry % 10);
cur = cur->next;
carry /= 10;
}
return dummy.next;
}
};
int main() {
Solution sol;
ListNode* l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
ListNode* l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
ListNode* result = sol.addTwoNumbers(l1, l2);
vector<int> expected = {7, 0, 8};
for (int val : expected) {
assert(result != nullptr && result->val == val);
result = result->next;
}
assert(result == nullptr); // End of list
return 0;
}