反转链表
1，使用栈解决
链表的反转是老生常谈的一个问题了，同时也是面试中常考的一道题。最简单的一种方式就是使用栈，因为栈是先进后出的。实现原理就是把链表节点一个个入栈，当全部入栈完之后再一个个出栈，出栈的时候在把出栈的结点串成一个新的链表。 原理如下
#include<iostream>
#include<stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* reverseList(ListNode* head)
{
stack<ListNode*> s;
//将链表节点一个个都放入栈中
while (head != NULL)
{
s.push(head);
head=head->next;
}
//判断栈是否为空
if (s.empty())
{
return NULL;
}
//放入栈中后，再挨个取出
//取出栈中第一个节点，作为逆置链表的头节点
ListNode* first = s.top();
s.pop();
//临时指针把节点连接起来
ListNode* temp = first;
//栈中元素挨个弹出
while (!s.empty())
{
temp->next = s.top();
s.pop();
temp = temp->next;
}
//注意要把之前链表的头节点的next指针指向NULL，否则会构成环
temp->next = NULL;
return first;//返回逆置链表头节点
}
};
//测试-----------------
void input(ListNode* l)
{
int num;
cin >> num;
if (num == -1)
return;
l->val = num;
ListNode* end = l;
while (1)
{
cin >> num;
if (num == -1)
return;
ListNode* newNode = new ListNode(num);
end->next=newNode;
end = newNode;
}
}
void display(ListNode* l)
{
if (l == NULL)
{
return;
}
while (l!=NULL)
{
cout << l->val;
l = l->next;
}
}
void test()
{
ListNode* l = new ListNode(0);
input(l);
Solution s;
l = s.reverseList(l);
cout << "链表打印：" << endl;
display(l);
cout << endl;
}
int main()
{
test();
system("pause");
return 0;
}
双链表求解
双链表求解是把原链表的结点一个个摘掉，每次摘掉的链表都让他成为新的链表的头结点，然后更新新链表。下面以链表1→2→3→4为例画个图来看下。
class Solution {
public:
ListNode* reverseList(ListNode* head)
{
//新链表---头插法完成链表逆置
ListNode* newList=NULL;
while (head)
{
//保存下一个节点
ListNode* nextNode = head->next;
//每次访问原链表的节点，该节点都会成为新链表的头结点
head->next = newList;
//更新新链表头节点位置
newList = head;
//head指向原链表当前遍历到的节点
head = nextNode;
}
return newList;
}
};递归解决
- 使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 retret .
- 此后，每次函数在返回的过程中，让当前结点的下一个结点的 nextnext 指针指向当前节点。
- 同时让当前结点的 nextnext 指针指向 NULLNULL ，从而实现从链表尾部开始的局部反转
- 当递归函数全部出栈后，链表反转完成。
class Solution {
public:
ListNode* reverseList(ListNode* head)
{
//递归退出条件：当前节点为空，返回到上一个节点的位置
if (head->next == NULL)
return head;//当最后一次递归到尾节点的时候，发现最后一个节点的next为NULL，因此返回最后一个节点赋值给ret,因此ret最后得到的就是尾节点
//通过不断的递归，找到倒数第二个节点
ListNode* ret=reverseList(head->next);//ret指针接收的是没有逆置前，链表中最后一个节点
//下面是递归完后，进行回溯的操作
head->next->next = head;
head->next = NULL;
return ret;
}
};双指针解决
- 定义两个指针： prepre 和 curcur ；prepre 在前 curcur 在后。
- 每次让 prepre 的 nextnext 指向 curcur ，实现一次局部反转
- 局部反转完成之后，prepre 和 curcur 同时往前移动一个位置
- 循环上述过程，直至 prepre 到达链表尾部
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur = NULL, *pre = head;
while (pre != NULL) {
ListNode* t = pre->next;
pre->next = cur;
cur = pre;
pre = t;
}
return cur;
}
};妖魔化的双指针
- 原链表的头结点就是反转之后链表的尾结点，使用 headhead 标记 .
- 定义指针 curcur，初始化为 headhead .
- 每次都让 headhead 下一个结点的 nextnext 指向 curcur ，实现一次局部反转 局部反转完成之后，curcur 和 headhead 的 nextnext 指针同时 往前移动一个位置
- 循环上述过程，直至 curcur 到达链表的最后一个结点 .
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL) { return NULL; }
ListNode* cur = head;
while (head->next != NULL) {
ListNode* t = head->next->next;
head->next->next = cur;
cur = head->next;
head->next = t;
}
return cur;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-03-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
