剑指offer24（反转链表）

2023-12-10 09:32

文章标签 链表反转 offer24

本文主要是介绍剑指offer24（反转链表），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode题解：剑指offer24（反转链表）

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路：

反转字符串的本质就是原链表的箭头反转，从尾结点开始向头结点遍历输出，将原链表中的箭头反转。因此需要三个指针，一个指向当前结点、一个指向当前结点的前一结点、一个指向当前结点的后一结点。

头文件如下：

#pragma once
#include<iostream>
using namespace std;
class Node{
public:int data;Node* next;
};
class Linklist {
public:Linklist();void Creatlist();void Showlist();Node* Reverselist();void Showreverselist(Node* n);
private:Node* head;
};

具体实现如下：

#include<iostream>
#include<ctime>
#include"反转链表元素.h"
using namespace std;
Linklist::Linklist()
{head = new Node;head->data = 0;head->next = NULL;
}
void Linklist::Creatlist()
{Node* p = head;int n = 5;for (int i = 0; i < n; i++){Node* q = new Node;q->data = rand() % 100;q->next = NULL;p->next = q;p = q;}
}
void Linklist::Showlist()
{Node* p = head;int i = 0;while (p->next != NULL){p = p->next;cout << p->data << "->";i++;}cout << "NULL"<<endl;
}
Node* Linklist::Reverselist()
{Node* p = head->next;Node* q = NULL;while (p != NULL){Node* temp = p->next;p->next = q;q = p;p = temp;}return q;
}
void Linklist::Showreverselist(Node* n)
{Node* p = n;int i = 0;while (p != NULL){cout << p->data <<"->";p = p->next;i++;}cout << "NULL" << endl;
}
int main()
{srand((unsigned int)time(NULL));Linklist l;l.Creatlist();l.Showlist();cout << "----------------------" << endl;Node* temp = l.Reverselist();l.Showreverselist(temp);
}