反转单链表

题目链接

下面主要介绍两种方法：

---

方法一：

利用三个指针变量进行反转

具体过程如图所示：

注意：循环的结束的条件为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)
{//如果链表为空，直接退出，返回NULLif (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;
}