Linked list problems look small, but they expose whether you can keep track of pointers under pressure. The three below cover a lot of ground: reversing links, checking symmetry, and detecting a cycle. Each solution keeps extra memory at O(1), and the code is short enough to reproduce from memory.
Reversing a singly linked list
The iterative version uses three pointers. pre points to the previous node in the reversed part, cur is the node being processed, and nxt temporarily stores the next node so the rest of the list is not lost. During each step, cur.next is pointed back to pre, then both pre and cur move forward. When the loop ends, pre is the new head.
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre = None
cur = head
while cur:
nxt = cur.next # store the next node
cur.next = pre # reverse the pointer
pre = cur # advance pre
cur = nxt # advance cur
return pre # return the new head
The recursive version follows the same idea but works from the end of the list back toward the front:
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
new_head = self.reverseList(head.next)
head.next.next = head
head.next = None
return new_head
After the sublist has been reversed, the node after head should point back to head, and then head.next must be set to None to close the reversed list.
Checking whether a linked list is a palindrome
A palindrome check can be done in O(1) extra space by combining two familiar linked-list techniques. First, use fast and slow pointers to find the middle. Then reverse the second half. Finally, compare nodes from the original head and the reversed second half. If every value matches until the second half is exhausted, the list is a palindrome.
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # when fast reaches the end, slow is at the middle
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre, cur = None, head
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:
return True
# 1 find the midpoint
mid = self.middleNode(head)
# 2 reverse the second half
head2 = self.reverseList(mid)
# 3 compare from both ends
cur1, cur2 = head, head2
while cur2:
if cur1.val != cur2.val:
return False
cur1 = cur1.next
cur2 = cur2.next
return True
This runs in O(n) time and uses O(1) extra space. The second half can be reversed back if the original list structure needs to be preserved, but the comparison itself does not require that step.
Detecting a cycle
Floyd's cycle detection uses two pointers moving at different speeds. slow moves one node at a time, while fast moves two. If there is a cycle, fast will eventually lap slow and meet it inside the cycle. If there is no cycle, fast will reach the end of the list first.
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast == slow:
return True
return False
The time complexity is O(n), and the extra space is O(1).
There is a useful follow-up: after a cycle has been detected, where does the cycle begin? Keep one pointer at the meeting point and move another pointer from the head. Advance both one step at a time. The node where they meet again is the entrance to the cycle.