每日一题（反转链表）

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

206. 反转链表 - 力扣（LeetCode）

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

思路一

运用迭代的算法，把头指针去指向空，再把第二个指针指向头指针依次类推，创造三个指针，不断地向后迭代一直都是第二个指针指向第一个指针，第三个指针，用来保存下一个指针。

struct ListNode* reverseList(struct ListNode* head) 
{
	if (head == NULL)
		return NULL;
	struct ListNode* n1, * n2, * n3;
	n1 = NULL;
	n2 = head;
	n3 = head->next;
	//n2为空，才是结束，不是n3为空
	while (n2 != NULL)
	{
		//翻转
		n2->next = n1;
		//迭代向后
		n1 = n2;
		n2 = n3;
		if (n3 != NULL)
		{
			n3 = n3->next;
		}
		return n;
	}
}

思路2

开辟一个新的链表，取原链表中的节点头插到新链表中

struct ListNode* reverseList(struct ListNode* head)
{
	struct ListNode* cur = head;
	struct ListNode* newhead = NULL;
	//当cur为空，结束循环
	while (cur != NULL)
	{
		//先把next贮存起来
		struct ListNode* next = cur->next;
		//头插
		cur->next = newhead;
		//迭代向后
		newhead = cur;
		next = cur;
	}
	return newhead
}