反转单链表
下面主要介绍两种方法：
方法一：
利用三个指针变量进行反转
具体过程如图所示：
注意：循环的结束的条件为cur == NULL而不是next == NULL
实现代码：
struct ListNode* reverseList(struct ListNode* head){ struct ListNode* newHead = NULL; struct ListNode* cur = head; while (cur) { struct ListNode* curNext = cur->next; //如果next放在循环外面定义，就不好控制循环结束条件 cur->next = newHead; newHead = cur; cur = curNext; } return newHead; }
方法二：
利用哨兵位实现反转
具体过程如图所示：
注1：循环结束的条件为cur->next == NULL
注2：返回之前要将哨兵位释放，防止内存泄露
实现代码：
struct ListNode* reverseList(struct ListNode* head) { //如果链表为空，直接退出，返回NULL if (head == NULL) return NULL; //创建哨兵为 struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode)); newHead->next = head; //实现反转 struct ListNode* cur = head; while (cur->next) { struct ListNode* curNext = cur->next; cur->next = curNext->next; curNext->next = newHead->next; newHead->next = curNext; } //释放哨兵位，返回新的头 struct ListNode* retHead = newHead->next; free(newHead); return retHead; }
