反转单向链表

反转单向链表

时间复杂度：O(N)

空间复杂度：O(1)

void reverse_list (node** head_ptr) {
	node* prev = NULL;
	node* curr = *head_ptr;
	node* next = NULL;
    
	while (curr != NULL) {
		next = curr->next;
		curr->next = prev;

		prev = curr;
		curr = next;
	}

	*head_ptr = prev;
}

a -> b -> c -> ... -> end

第一次循环:

curr指向a，next指向b，curr->next 指向NULL(prev)。此时没有节点指向b，但next记录了b，所以curr可以通过next变量指向b。在此之前，将prev更新为a。

第二次循环：

初始curr指向b，prev指向a；更新next指向c，curr->next(即b->next)指向prev(a)。此时的链表变成两部分：一部分是NULL <- a <- b; 另一部分是c -> ... -> end.

直到最后一次循环结束时，prev指向end，curr(以及next)指向NULL。

循环结束，此时只剩下一条链表: NULL <- a <- b <- ... <- end.

改变初始头节点为prev(end),即完成链表反转。