1. Reversing a singly-linked list:

(a) *Iterative method*: maintain three pointers, two to the nodes being reversed, and one to the next node to be reversed. Continue reversing nodes till the current node goes past the last node.

void reverse() {
if (head == NULL || head->next == NULL) return;
ListNode *prev = head, *curr = head->next, *next = (head->next)->next;
while (curr != NULL) {
curr->next = prev;
if (prev == head) prev->next = NULL; // loop otherwise
prev = curr; curr = next;
if (next != NULL) next = next->next;
}
ListNode *n = head;
head = tail;
tail = n;
}

Continue reading →