2-6 链表逆序

我只介绍两种常用方法吧，非递归方法和递归方法我觉得够用就行

1、非递归方法：

将第二个元素后面的元素依次插入到头结点后面，

最后再把原始第一个元素放到原始第二个元素后面，整个链表就能够反转了

这个方法对于带不带头结点的链表都适用：

①不带头结点

原始链表，其中第二个元素是 B

A -> B-> C -> D -> E -> F -> null

先进入循环,不断的把B的后继元素往第一个元素后面插

A -> C -> B -> D -> E -> F -> null #将上面 B后的C 插入到A后面

A -> D -> C -> B -> E -> F -> null #将上面 B后的 D 插入到A后面

A -> E -> D -> C -> B -> F -> null #将上面 B后的 E 插入到A后面

A -> F -> E -> D -> C -> B -> null #将上面 B后的 F 插入到A后面

最后将A放到B后面：

F -> E -> D -> C -> B -> A -> null


void Reverse(node **h) {if ((*h) == nullptr)return;else if ((*h)->next == nullptr)return;else {node *r=nullptr, *p1 = (*h), *p2 = (*h)->next;while (p2->next != nullptr) {//由于p2一直固定在原始的第2个元素//所以r一直都是取紧接着原始的第2个元素右侧的那个元素地址r = p2->next;p2->next = r->next;//将r插入到第1个元素后面，这里因为第1个元素的位置P1也不变，所以也很简单r->next = p1->next;p1->next = r;}//最后再来处理原始的第1个元素P1 和 原始的第2个元素P2的顺序p2->next = p1;(*h) =p1->next;p1->next = nullptr;}
}

②带头结点的链表

可以将头结点视为第一个元素，那么就是直接把 A 的后继元素不断的往head后面插：

带头结点原始链表，将头结点视为第1个元素，那么其中第2个元素是 A

Head -> A -> B -> C -> D -> E -> F -> null

先进入循环,不断的把A的后继元素往头结点后面插

Head -> B -> A -> C -> D -> E -> F -> null

Head -> C -> B -> A -> D -> E -> F -> null

Head -> D -> C -> B -> A -> E -> F -> null

Head -> E -> D -> C -> B -> A -> F -> null

Head -> F -> E -> D -> C -> B -> A -> null

只不过最后不用将第一个元素放到A后面，也就是不用修改头指针

void Reverse(node *h) {if (h->next == nullptr) {cout << "这是空表！" << endl;return;}else if (h->next->next == nullptr) {cout << "只有一个元素，无需反转！" << endl;return;}else {node *p2 = h->next;//将头结点视为第1个元素，那么数据首节点就视为第2个元素node *r;/*将第二个元素后面的元素依次插入第一个元素后面*/while (p2->next != nullptr) {//由于p2一直固定在原始的第2个元素//所以r一直都是取紧接着原始的第2个元素右侧的那个元素地址r = p2->next;p2->next = r->next;//将r插入到头结点后面r->next = h->next;h->next = r;}//最后与不带头结点的单链表的区别就是，不用修改头指针了}
}

2、递归方法

①不带头结点

递归其实就是一直要找到最后一个结点，然后每次改一下，

这个时候其实函数递归的时，函数用栈存储了前面每个结点的信息，所以一步一步从最后面改动到前面去，图我也就不画了，

画起来麻烦，可以参考一下这个博文的图，https://blog.csdn.net/fx677588/article/details/72357389，

node* ReverseList_Recursion(node *p) {/*结束的条件:链表为空或者链表最后一个节点*/if (p == nullptr || p->next == nullptr) {return p;}//递归调用node *NewHead = ReverseList_Recursion(p->next);//每次都把当前结点 重新设置成 当前结点的下一个结点的下一个结点p->next->next = p;//然后再把当前结点的新后继设置为空，相当于当前结点时新链表的尾结点p->next = nullptr;return NewHead;
}

要调用此函数的时候，假设已经存在单链表的头指针：list1_h;

直接：node * list_2 = ReverseList_Recursion( list1_h );

这样新的头指针list_2就是反转后的链表的头指针