鹅厂是一家能让你拥有多元化职业发展的平台。尊重个性、轻松自在的工作环境、有趣的互联网工作。在鹅厂这家拥有海量用户基础的公司工作，能得到互联网应用最前沿的视野、获得好的专家辅导。小编从今天开始就会陆续作死挑战鹅厂面试题，并持续为大家更新！

题目

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

思路

单链表，官方释义为：是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。如图：

单链是单向的，只能单向访问，现需要将链表翻转过来，也就是说next指针要反向。

1、简单思路：

当然这里有个简单的思路：遍历一遍链表，将每个元素都存储进vector容器，然后反向迭代vector的每个元素，并将元素的next指针指向容器中前一个元素。这是最简单的方式，实现起来也十分好理解；

ListNode* reverseList(ListNode* head) {
	
	if(head == NULL)return NULL;
	vector<ListNode*> vec ;
	ListNode* node_head = head ;
	while (node_head->next!=NULL)
	{		
		vec.push_back(node_head);
		node_head = node_head->next ;
	}
	vec.push_back(node_head);
	auto iter = vec.rbegin();
	while (iter != vec.rend())
	{
		if(iter+1!=vec.rend())(*iter)->next = *(iter+1);
		else (*iter)->next = NULL ;
		iter ++ ;
	}
	return node_head;
}

但是这种方式并不是鹅厂想要的，因为他们想考的是面试者对链表数据结构的理解程度，以及逻辑思维的深度。

2、从链表角度的思路

单链表反转，我们需要处理的就是当前节点、当前节点前一个节点、当前节点后一个节点，这三个节点之间的逻辑关系（node_head、node_temp_pre、node_temp_next）。其实我们只需要将头指针逐步顺着链表往后移，并且在移动过程中，改变next的指向。

思路实现关键点：

首先我们得在改变当前节点next指向之前将next指向的节点访问出来并通过指针保存起来，不然当当前节点的next指向改变再来访问就访问不到了

然后将next指向node_temp_pre（之前保存的前一个节点）

再然后要做好准备将head往后移动一位，将当前节点赋值给node_temp_pre，作为后续节点的next节点

最后移动head

题解

ListNode* reverseList(ListNode* head) {
	if(head == NULL)return NULL;
	ListNode* node_head = head ;
	ListNode* node_temp_pre = NULL ;
	ListNode* node_temp_next = NULL ;
	while(node_head->next!=NULL)
	{				
		node_temp_next = node_head->next;
		node_head->next = node_temp_pre ;
		node_temp_pre = node_head ;
		node_head = node_temp_next; 
	}
	node_head->next = node_temp_pre;
	return node_head;
}