反转链表的递归与非递归实现（C++描述）

给定一个单向链表的头结点，要求将链表反转，并返回新的头结点。

一、迭代实现

思路：遍历链表，依次调整每个节点的指针域。

定义 结点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即为反转后链表的新头结点！

代码实现：

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;
}

参考：

链表反转的图文讲解（递归与迭代两种实现）

原文链接: https://www.cnblogs.com/liuzhuan-xingyun/p/13620866.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍