Skip to main content

One Pass

One pointer​

Array to Linked List​

Easy·
FIG. ARRAY TO LINKED LIST● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • A single loop builds one node per remaining value in arr, n = len(arr).
Space
O(1)
  • Only head and curr are tracked; the newly allocated list nodes are the required output, not auxiliary space.
def array_to_linked_list(arr):
head = ListNode(arr[0])
curr = head
for i in range(1, len(arr)):
curr.next = ListNode(arr[i])
curr = curr.next
return head

1290. Convert Binary Number in a Linked List to Integer​

Easy·
2 Approachesclick to switch
FIG. CONVERT BINARY NUMBER IN A LINKED LIST T● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • curr walks the list once, n being the number of nodes.
Space
O(1)
  • Only number and curr are kept, regardless of list length.
def getDecimalValue(head):
number = 0
curr = head
while curr:
number = number * 2 + curr.val
curr = curr.next
return number

3263. Convert Doubly Linked List to Array I​

2 Approachesclick to switch
FIG. CONVERT DOUBLY LINKED LIST TO ARRAY I● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • n is the number of nodes - the while curr loop advances curr one node at a time, visiting each node once.
Space
O(n)
  • array collects one entry per node, growing to n values.
def toArray(head):
array = []
curr = head
while curr:
array.append(curr.val)
curr = curr.next
return array

3294. Convert Doubly Linked List to Array II​

Medium·
2 Approachesclick to switch
FIG. CONVERT DOUBLY LINKED LIST TO ARRAY II● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • The first while walks backward from head to the true start of the list, and the second walks forward from head.next to the end - together the two loops visit every one of the n nodes in the list exactly once, with no overlap.
Space
O(n)
  • array accumulates one entry per node, up to n elements.
def toArray(head):
array = collections.deque()
curr = head
while curr:
array.appendleft(curr.val)
curr = curr.prev
curr = head.next if head else None
while curr:
array.append(curr.val)
curr = curr.next
return array

237. Delete Node in a Linked List​

Medium·
FIG. DELETE NODE IN A LINKED LIST● INTERACTIVE
visualization loads as you reach it
Time
O(1)
  • node's value and next pointer are each overwritten once from node.next, independent of the list's length.
Space
O(1)
  • No extra structures are allocated.
def deleteNode(node):
node.val = node.next.val
node.next = node.next.next

Search In Linked List​

Basic·
FIG. SEARCH IN LINKED LIST● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • n = number of nodes in head. The while head loop walks the list once, stopping as soon as head.data == x matches or the list ends.
Space
O(1)
  • Only the head traversal pointer is used; nothing scales with n.
def searchLinkedList(head, x):
while head:
if head.data == x:
return True
head = head.next
return False

Is Linked List Length Even?​

Basic·
FIG. IS LINKED LIST LENGTH EVEN● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • The while head loop advances head and increments length once per node, visiting each of the n nodes exactly once.
Space
O(1)
  • Only the length counter is tracked; no extra structure is allocated.
def isLengthEven(head):
length = 0
while head:
head = head.next
length += 1
return length % 2 == 0

Frequency in a Linked List​

Easy·
FIG. FREQUENCY IN A LINKED LIST● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • A single pass walks head to the end of the list, n nodes.
Space
O(1)
  • Only the count accumulator is tracked.
def count(head, key):
count = 0
while head:
count += head.data == key
head = head.next
return count

Modular Node​

Basic·
FIG. MODULAR NODE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • n is the number of nodes in the list. The while curr loop advances curr once per node, doing constant work per step.
Space
O(1)
  • Only mod_node, curr, and index are tracked, regardless of list length.
def modularNode(head, k):
mod_node = None
curr = head
index = 1
while curr:
if index % k == 0:
mod_node = curr
curr = curr.next
index += 1
return mod_node.data if mod_node else -1

Remove Nodes​

203. Remove Linked List Elements​

Easy·
2 Approachesclick to switch
FIG. REMOVE LINKED LIST ELEMENTS● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • current_node walks the list once via current_node.next, visiting each of the n nodes.
Space
O(1)
  • Only sentinel and current_node are tracked, regardless of n.
def removeElements(head, val):
sentinel = ListNode(None, next=head)
current_node = sentinel
while current_node and current_node.next:
if current_node.next.val == val:
current_node.next = current_node.next.next
else:
current_node = current_node.next
return sentinel.next

83. Remove Duplicates from Sorted List​

2 Approachesclick to switch
FIG. REMOVE DUPLICATES FROM SORTED LIST● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • current_node walks the list once, visiting each node exactly once.
Space
O(1)
  • Duplicates are unlinked in place; only current_node is tracked.
def deleteDuplicates(head):
current_node = head
while current_node and current_node.next:
if current_node.val == current_node.next.val:
current_node.next = current_node.next.next
else:
current_node = current_node.next
return head

1474. Delete N Nodes After M Nodes of a Linked List​

Easy·
FIG. DELETE N NODES AFTER M NODES OF A LINKED● INTERACTIVE
visualization loads as you reach it
Time
O(L)
  • The outer while keeps advancing p through the "keep" loop or deleting via p.next = p.next.next through the "delete" loop - every node in the original list is either advanced past or unlinked exactly once, so total work across all inner loops is bounded by the list length L.
Space
O(1)
  • Only sentinel and p are allocated; nodes are deleted in place with no extra structure.
class Solution:
def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:
sentinel = ListNode(None, head) # Sentinel node
p = sentinel
while p and p.next:
for _ in range(m):
if p:
p = p.next
for _ in range(n):
if p and p.next:
p.next = p.next.next
return sentinel.next

Modify Nodes​

2046. Sort Linked List Already Sorted Using Absolute Values​

Medium·
FIG. SORT LINKED LIST ALREADY SORTED USING AB● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • current_node advances past each node exactly once; a negative node is unlinked and reinserted at the front in O(1), without restarting the scan.
Space
O(1)
  • Only sentinel, current_node, and next_node are tracked; nodes are relinked in place.
def sortLinkedList(head):
sentinel = ListNode(None, next=head)
current_node = sentinel.next
while current_node and current_node.next:
if current_node.next.val < 0:
next_node = current_node.next
current_node.next = next_node.next
next_node.next = sentinel.next
sentinel.next = next_node
else:
current_node = current_node.next
return sentinel.next

Counter​

3063. Linked List Frequency​

Easy·
2 Approachesclick to switch
FIG. LINKED LIST FREQUENCY● INTERACTIVE
visualization loads as you reach it
Time
O(n + k)
  • The first while curr loop walks all n nodes of the input list to build counter - one pass.
  • The for freq in counter.values() loop then walks the k distinct values to build the frequency list - a second pass.
Space
O(k)
  • counter holds one entry per distinct value, and the new frequency list built from sentinel also has k nodes.
def frequenciesOfElements(head):
counter = Counter()
curr = head
while curr:
counter[curr.val] += 1
curr = curr.next
sentinel = ListNode(None)
curr = sentinel
for freq in counter.values():
curr.next = ListNode(freq)
curr = curr.next
return sentinel.next