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 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) |
# |-------------|-----------------|--------------|
nums = [1, 2, 6, 3, 4, 5, 6]
val = 6
head = list_from_array(nums)
print(head)
# 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6
print(removeElements(head, val))
# 1 -> 2 -> 3 -> 4 -> 5
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¶
"""
- Reverse a singly linked list.
"""
from typing import Optional
from leetpattern.utils import ListNode
# Iterative
def reverseListIterative(head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
prev = None
while cur:
temp = cur.next
cur.next = prev
prev = cur
cur = temp
return prev
# Recursive
def reverseListRecursive(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)
nums = [1, 2, 3, 4, 5]
head1 = list_from_array(nums)
print(head1)
# 1 -> 2 -> 3 -> 4 -> 5
print(reverseListIterative(head1))
# 5 -> 4 -> 3 -> 2 -> 1
head2 = list_from_array(nums)
print(reverseListRecursive(head2))
# 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 ListNode
def deleteNode(node: ListNode) -> None:
node.val = node.next.val
node.next = node.next.next
head = list_from_array([4, 5, 1, 9])
node = head.next
deleteNode(node)
print(head) # 4 -> 1 -> 9
2487. Remove Nodes From Linked List¶
"""
- Remove all nodes from a linked list that have a value greater than `maxValue`.
"""
from typing import Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
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:
head = list_from_array([5, 2, 13, 3, 8])
assert (list_to_array(remove_nodes_recursive(head))) == [13, 8]
head = list_from_array([5, 2, 13, 3, 8])
assert (list_to_array(remove_nodes_iterative(head))) == [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 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
listA = [4, 1, 8, 4, 5]
listB = [5, 6, 1, 8, 4, 5]
headA = list_from_array(listA)
print(headA)
# 4 -> 1 -> 8 -> 4 -> 5
headB = list_from_array(listB)
print(headB)
# 5 -> 6 -> 1 -> 8 -> 4 -> 5
headA.intersect(headB, 8)
print(getIntersectionNodeHash(headA, headB))
# 8 -> 4 -> 5
print(getIntersectionNodeTP(headA, headB))
# 8 -> 4 -> 5
141. Linked List Cycle¶
"""
- Determine if a linked list has a cycle in it.
"""
from typing import Optional
from leetpattern.utils import ListNode
def hasCycle(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
print(hasCycle(list_from_array([3, 2, 0, -4]))) # False
print(hasCycle(list_from_array([3, 2, 0, -4], 1))) # True
#include <cassert>
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
bool hasCycle(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 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.hasCycle(head) == true);
ListNode* head2 = new ListNode(1);
head2->next = new ListNode(2);
assert(sol.hasCycle(head2) == false);
ListNode* head3 = new ListNode(1);
assert(sol.hasCycle(head3) == false);
return 0;
}
142. Linked List Cycle II¶
"""
- Given a linked list, return the node where the cycle begins. If there is no cycle, return `None`.
"""
from typing import Optional
from leetpattern.utils import 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
head1 = list_from_array([3, 2, 0, -4], 1)
print(detectCycle(head1).val) # 2
head2 = list_from_array([3, 2, 0, -4])
print(detectCycle(head2)) # None
#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¶
"""
- Given a number represented as a linked list, double it and return the resulting linked list.
"""
from typing import Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
def doubleIt(head: Optional[ListNode]) -> Optional[ListNode]:
def twice(node):
if not node:
return 0
doubled_value = node.val * 2 + twice(node.next)
node.val = doubled_value % 10
return doubled_value // 10
carry = twice(head)
if carry:
head = ListNode(val=carry, next=head)
return head
def test_doubleIt() -> None:
head = list_from_array([9, 9, 9])
assert (list_to_array(doubleIt(head))) == [1, 9, 9, 8]
2. Add Two Numbers¶
"""
- Represent the sum of two numbers as a linked list.
"""
from typing import Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
# Linked List
def add_two_numbers(
l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
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 = list_from_array([2, 4, 3])
l2 = list_from_array([5, 6, 4])
result = add_two_numbers(l1, l2)
assert list_to_array(result) == [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;
}