Draw the pointers before changing them. A dummy node before the head removes the special case of editing the head. Fast/slow pointers find the middle (fast moves two steps) and detect cycles (they meet inside a loop).
Template · O(n) time, O(1) space
defreverse(head):
prev, cur =None, head
while cur:
nxt = cur.next # save before overwriting
cur.next = prev
prev, cur = cur, nxt
return prev
ListNode*reverse(ListNode*head) {
ListNode* prev =nullptr;
while (head) {
ListNode* nxt = head->next; // save before overwriting
head->next = prev;
prev = head;
head = nxt;
}
return prev;
}
Common pitfalls
Losing the rest of the list by overwriting next before saving it