LeetCode-206 Reverse Linked List

概述题目描述如下 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 bot 题目描述如下

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;    }};

总结

以上是内存溢出为你收集整理的LeetCode-206 Reverse Linked List全部内容，希望文章能够帮你解决LeetCode-206 Reverse Linked List所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。