题目描述如下
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list
逆转链表，其实就是先进后出，所以可以用栈实现。当然简单的头插法也可以，这里就不写了。
/**
* 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<ListNode *> nodeStack;
if(head==NULL)
return NULL;
ListNode * pNode=head;
while(pNode!= NULL)
{
nodeStack.push(pNode);
pNode=pNode->next;
}
ListNode * newHead=NULL;
newHead=nodeStack.top();
nodeStack.pop();
ListNode * pre=newHead;
while(!nodeStack.empty())
{
ListNode * p=nodeStack.top();
nodeStack.pop();
pre->next=p;
pre=p;
}
pre->next=NULL;
return newHead;
}
};递归本质也是一个栈结构，所以也可以用递归实现，这里记录一下：
/**
* 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 * newHead=NULL;
if(head ==NULL) //链表是空的就返回空
return NULL;
ListNode * nextNode = head->next;
ListNode * res=reverseList(nextNode);
if(nextNode ==NULL)
return head;
nextNode->next = head;
head->next=NULL;
return res;
}
};内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
