剑指 Offer 24. 反转链表

剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

解题思路

用一个栈存储了数据元素，然后正常地创建列表并赋值
实现过程中对链表的创建和操作很不熟悉，需要仔细地复习一下

代码

/**
* Definition for singly-linked list.
* struct ListNode {
*
int val;
*
ListNode *next;
*
ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
stack<int> s;
ListNode* q=head;
while(q!=nullptr){
s.push(q->val);
q=q->next;
}
ListNode* head1=new ListNode;
if(s.empty()==false){
head1->val=s.top();
head1->next=nullptr;
s.pop();
}
else {
head1=nullptr;
}
ListNode* p=head1;
while(s.empty()==false){
ListNode* temp=new ListNode;
temp->val=s.top();
temp->next=nullptr;
s.pop();
p->next=temp;
p=p->next;
}
return head1;
}
};

解题思路

另一种思路，使用了三个指针p,q,k来完成，p保存第一个节点，q保存第二个节点，k保存第三个节点。让q的next指向p,如果是头节点，p的next指向nullptr，然后让p指向q,q指向k，k指向k的next，循环，直到k指向最后一个节点，返回k。需要判断，如果链表长度小于3，需要做相应的处理然后返回。

代码

/**
* Definition for singly-linked list.
* struct ListNode {
*
int val;
*
ListNode *next;
*
ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* p=head;
if(head==nullptr){
return nullptr;
}
else if(head->next==nullptr){
return p;
}
else if(head->next->next==nullptr){
ListNode* q=p->next;
q->next=p;
p->next=nullptr;
return q;
}
ListNode* q=p->next;
ListNode* k=p->next->next;
while(k!=nullptr){
q->next=p;
if(p==head){
p->next=nullptr;
}
p=q;
if(k->next==nullptr){
k->next=q;
break;
}
q=k;
k=k->next;
}
return k;
}
};

/**
* Definition for singly-linked list.
* struct ListNode {
*
int val;
*
ListNode *next;
*
ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pnode=head;
ListNode* pre=nullptr;
ListNode* rev=nullptr;
while(pnode!=nullptr){
ListNode* pnext=pnode->next;
if(pnext==nullptr){
rev=pnode;
}
pnode->next=pre;
pre=pnode;
pnode=pnext;
}
return rev;
}
};

最后

以上就是顺利衬衫为你收集整理的剑指 Offer 24. 反转链表的全部内容，希望文章能够帮你解决剑指 Offer 24. 反转链表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。