6-1 单链表逆转

6-1 单链表逆转
https://pintia.cn/problem-sets/15/problems/724

挺基础的一道题，没有什么难点，但是要注意几种边界情况，如Reverse什么时候对链表处理，什么时候直接返回即可；如果要逆转链表，什么时候需要结束（逆转完了/不能再遍历了）？结束后有没有节点需要处理？

遇到这道题第一反应就是怎么样实现每次都能找到当前尾节点的前一个节点，想到过遍历同时保存每个节点地址到数组里等等，后来意识到其实整个过程可以一次遍历完成逆转，只需要遍历的同时进行处理即可：

1. 思路

首先，考虑什么时候不需要处理。链表的问题如果不考虑到这步，可能会直接访问next节点引发出错（这一题好像不会，但最好还是提前考虑到）。很容易想到，如果链表为空、或者链表只有一个节点时，不需要进行逆转，直接返回即可。于是有如下代码：

if (L == NULL|| L->Next==NULL)
{
	return L;
}

其次，是逆转的处理过程：一次遍历完成逆转，需要3个指针，一个指针now指向L的当前头节点、一个指针L2指向新链表L2的头节点，最后是一个指向L2之前节点的next指针，用来每次记录L2最新节点的next。

初始状态 初始状态：now指向L的头节点，L2、next（next=L2）暂时为空。

L2指向新的头节点 找到L2链表下一个节点：这一步执行L2 = now，L2指向最新节点，next指向L2链表的剩余部分头节点（目前为空）。

now指向下一个节点 now更新节点：执行now = now->Next，将now指向剩余的L1链表部分头节点。

L2的next指向旧L2链表 串连L2链表：头节点（L2指向的节点）的指针指向L2链表的剩余部分，也就是next指向的节点（目前为空），从而完成L2链表的合并，构成目前完成的L2链表。

上面是一轮的步骤，每轮把一个节点添加到L2链表的头部。重复以上过程，就可以完成链表的逆转。类似于用旧墙砌新墙：每次把A墙的最上面的石头放到B墙，不断重复，A墙最上面的石头将会被放到B墙最下面，A墙最下面的石头最后放在B墙的最上面。
另外最后当now为空时将会退出循环，此时L1链表已经没有节点了，没有剩余的节点需要考虑。（相反，如果是两个有序链表的合并，就需要考虑）

2.代码

List Reverse(List L) {
	//没有or只有一个节点时不需要逆转
	if (L == NULL|| L->Next==NULL)
	{
		return L;
	}

	List L2 = NULL, next = NULL;
	List now = L;
	while (now)
	{
		next = L2;
		L2 = now;
		now = now->Next;
		L2->Next = next;
	}
	return L2;
}