反转链表的递归与非递归实现（C++描述）
2021-03-28 21:27
标签：tno blank art head 头结点 tps 回溯 初始 list 给定一个单向链表的头结点，要求将链表反转，并返回新的头结点。 思路：遍历链表，依次调整每个节点的指针域。 定义 结点p指向当前节点 结点q指向当前节点的下一个结点（p->next非空时） 结点r指向当前节点的前一个结点 节点newhead指向新头结点（） 初始 p=head,q=NULL，r = NULL; 当p不为空时： 如果p->next非空 q = p->next p->next = r r = p p = q 最后r即为反转后链表的新头结点！ 代码实现： 迭代法实现是顺序遍历从头到尾改变指针指向，递归的特性是回溯，采用从后向前改变指针指向的方式来实现链表反转。 链表反转的图文讲解（递归与迭代两种实现） 反转链表的递归与非递归实现（C++描述） 标签：tno blank art head 头结点 tps 回溯 初始 list 原文地址：https://www.cnblogs.com/liuzhuan-xingyun/p/13620866.html一、迭代实现
Listnode * ReverseList(Listnode *head){
if(head->next == NULL) return head;
Listnode *p,*q,*r;
p=head;q=r=NULL;
while(p!=NULL){
//if(p->next!=NULL)
q = p->next;
p->next = r;
r = p;
p = q;
}
return r;
}
二、递归实现
ListNode* reverse(ListNode* H) {
//包括特殊情况
if (H == NULL || H->next == NULL)
return H;
ListNode *newH = reverse(H->next);//注意,此处的操作是一直循环到链表末尾
H->next->next = H;//反转每个节点的指向
H->next = NULL;
return newH;
}
参考：
文章标题：反转链表的递归与非递归实现（C++描述）
文章链接：http://soscw.com/index.php/essay/69224.html