链表操作：反转链表

反转链表是一个挺有趣的问题。我们可以化为两个链表的衔接和断开问题。

为了形象说明假设有两条链表L1和L2（转换过程中只有一条），以蓝色的节点为L1的节点，红色的节点为L2的节点。其中L2为L1的反转链表。

要从L1转换到转换到L2。可以看出从L1开始截取当前一个节点作为L2的头，被截取节点的下一节点为，L1的新头，然后把L1的心头指向L2的头，不断重复直到转换完毕，说的比较抽象下面用图来说明。

① ② ③ 好了，就到这里不演示全部转换过程，可以看到在转换过程中是原链表发生了断裂。 从图可以看出，这是可以通过遍历L1来完成转换。那么就有两个问题要解决。

①在遍历过程中转换形式？②如何设置转换结束条件，以及转换开始前需要什么条件（一定是单纯的遍历一遍吗？）？

①在遍历过程中转换形式？

为了使得链表能够连接上，我们需要保存断开处，两侧的节点信息，同时为了使得能够用循环进行转换，我们还需要保存新链表头的后继节点。 分别用pre,pnode,pnext，三个指针来寻址。

以上图为例，转换过程的逻辑

pnode->next = pre; pre = pnode; pnode = pnext; pnext = pnext->next;

可以在纸上画一画过程，很直观。

②如何设置转换结束条件，以及转换开始前需要什么条件（一定是单纯的遍历一遍吗？）？

我们看看初始的时候各个指针的状态应该怎么样？ 为了让反转的链表有有尾节点，所以初始pre指针指向NULL，pnode指向初始的头,pnext指向pnode->next。

结束条件呢？看上图，当我们发现pnext指向NULL的时候，pnode已经是原链表的尾节点，新链表的头节点了，此时我们可以用一个preverhead节点来记录。当再次进行转换时，pnode就指向了空。 而pnode==NULL就是循环结束条件。 其实可以发现，最后pre指向了反转后的链表的头指针，我们也不一定要用一个额外的指针来记录新的头，但为了好理解。

下面上代码

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { ListNode* pre = NULL; ListNode* pnode = pHead; ListNode* preverhead = NULL; while(pnode != NULL)//循环结束条件尾pnode == NULL { ListNode* pnext = pnode->next; if(pnext == NULL)//如果pnode指向了原链表的尾 preverhead = pnode; pnode->next = pre; pre = pnode; pnode = pnext; } return preverhead; } };