reverse_list

reverse_list.cpp

void reverse_list(Node* head) {
	//Make sure we are not trying to reverse an empty list or a singleton
	if (head != NULL && head->next != NULL) {
		Node* curr = head;
		Node* next = head->next;
		Node* nextNext = NULL;

		//Initial state
		//[0] -> [1] -> [2] -> ... -> [n] -> NULL
		//head   next
		//curr

		//Keep inverting till the end
		while (next != NULL) {
			//Save the next's next so we can advance our pointer later
			nextNext = next->next;
			//Reverse next to curr
			next->next = curr;
			//Advances one position with the algorithm
			curr = next;
			next = nextNext;
		}

		//State right after the reversion
		//[0] <-> [1] <- [2] <- ... <- [n-1] <- [n]
		//head                                  curr

		//Since we did not invert the head itself the nodes [0] and [1]
		//point to each other. Using this in our favor we can now redirect
		//the head->next->next to the last node

		head->next->next = curr;
		//         /----------------------------v
		//[0] -> [1] <- [2] <- ... <- [n-1] <- [n]
		//head                                 curr

		//This seems weird, but actually we want to swap the contents
		//of [0] and [n] and then correct the pointers to create our reversed list

		head->next = curr->next;
		// /--------------------------\
                // |       /-------------------v--------v
		//[0]    [1] <- [2] <- ... <- [n-1] <- [n]
		//head                                 curr

		curr->next = NULL;

		// /-------------------------\
                // |       /------------------v--------v
		//[0]    [1] <- [2] <- ... <-[n-1]    [n] -> NULL
		//head                                curr

		//swap data
		int headData = head->data;
		head->data = curr->data;
		curr->data = headData;

		// /-------------------------\
                // |       /------------------v--------v
		//[n]    [1] <- [2] <- ... <-[n-1]    [0] -> NULL
		//head                                curr

		//Finally we can see that the resulting list is actually the reversed list
		//NULL <- [0] <- [1] <- [2] <- ... <- [n]
		//                                    head
	}
}