单链表的就地逆置学习笔记

算法思想：先假定有一个函数，可以将以head为头结点的单链表逆序，并返回新的头结点。利用这个函数对问题进行求解：将链表分为当前表头结点和其余部分，递归的过程就是，先将表头结点从链表中拆出来，然后对其余部分进行逆序，最后将当前的表头结点链接到逆序链表的尾部。递归的终止条件就是链表只剩一个节点时，直接返回这个节点。
原作者写的感觉比较粗略，我对代码部分加上了自己的理解。

/* dfs深度遍历这个单链表在递归的时候，不作处理在回溯时，标记回溯开始的位置（新的头结点），将节点和节点的下一节点逆置，将新的头结点传递给上一层递归，接下来逆置上一个节点和上一节点的下一个节点（逆置已逆置链表的尾节点），并传递标记的头结点，直到回溯完成我们就得到了逆转的单链表和它的头结点 dfs(当前状态) { if(边界状态)//head==NULL说明链表为空，不用处理, 从头到尾我们需要处理的最后一个节点是倒数第二个节点，将它和倒数第一逆置，因此，遍历到倒是第一个节点就是边界条件 { 记录//标记头结点位置并传递(这里选用返回值，还可以通过全局变量）给上一层递归 } dfs(下一状态) //回溯部分//节点和下一节点（逆置这已逆置链表的尾结点和），将新的头结点传递给上一层递归 } *///单链表原地逆置递归法（不带头结点），带头结点要单独处理头结点 //分析这个递归不要乱，每次进入递归就要从代码第一行开始看！即从LNode * Converse(LinkList &head)看，认清楚现在的参数是哪个结点 //这个函数执行完，要执行遍历得用newhead指针，不能再用head指针 LNode * Converse(LinkList &head){ if (head==NULL || head->next==NULL)//临界条件，若为空表，或者下一个结点为空（即递归到链表最后一个结点） { return head; //不能写return NULL; } LNode *newhead=Converse(head->next); //递归到链尾 //例子：x1->x2->x3->x4 //把Converse(head->next)整个看成一个指针，从临界条件看它将返回head给newhead。如上述例子，当递归函数走到x4，x4->next=NULL,所以将 //返回x4给newhead。 //coutdata<<" "<data; //回溯：将当前表头结点(head所指向的结点)链接到已经当前已经逆序链表的尾部. //根据分析此时的head应该是指x3,x3->next是x4(新链表的头) head->next->next=head; //将x4指向x3，即实现：从右往左连接 head->next=NULL; //将从x3指向x4的指针断掉，即实现：断掉从左到右的连接。到此实现了x4->x3->NULL,此时newhead指向x4,head指向x3. return newhead; //递归走到最后当前层的最后一部即将返回时如果觉得混乱，不知道该到哪个结点就想想当前结点是从哪来的。 //上两部的head是x3,而x3是从x2来的，所以应该返回到converse(x2), //所以是继续执行x2->next->next=x2（即x3指向x2，此时即有x4->x3->x2)，再x2->next=NULL（将x2指向x3的指针断掉) }

【单链表的就地逆置】