0.从尾到头打印单链表
单链表:一般给的都是无头节点的
另外:在面试中,如果我们打算修改输入的数据,则最好问一下面试官是不是允许修改
下面这种先把链表节点的值按链表序放到数组中,然后来一个算法库中的reverse属实有点流氓!不可取!
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:vector<int> reversePrint(ListNode* head) {ListNode* cur=head;vector<int> v;while(cur){v.push_back(cur->val);cur=cur->next;}v.reverse(v.begin(),v.end());//先放到数组,然后逆置return v;}
};
1.修改链表的方法
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:vector<int> reversePrint(ListNode* head) {//链表逆置ListNode* prev=nullptr;ListNode* cur=head;while(cur){ListNode* next=cur->next;cur->next=prev;prev=cur;cur=next;}head=prev;//头节点的指针现在是prev的位置cur=head;vector<int> v;while(cur){v.push_back(cur->val);cur=cur->next;}return v;}
};
2.不修改链表的方法-栈
/*** Definition for singly-linked list.单链表:一般给的都是无头节点的* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:vector<int> reversePrint(ListNode* head) {stack<ListNode*> st;vector<int> v;ListNode* cur=head;while(cur!=nullptr){st.push(cur);cur=cur->next;}while(!st.empty()){cur=st.top();v.push_back(cur->val);st.pop();}return v;}
};
3.不修改链表的方法-递归
由于递归本身就是栈结构,自然想到用递归来实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
//vector<int> v; 不能定义在这里
class Solution {
public:vector<int> v;vector<int> reversePrint(ListNode* head) {//vector<int> v;不能定义在这里if(head!=nullptr){if(head->next!=nullptr){reversePrint(head->next);}v.push_back(head->val);}return v;}
};
注意这里定义vector< int>的两个坑:
坑1:在递归这里我们不能vector定义的成局部的
坑2:不能定义成全局的,我猜测这里是因为力扣OJ在设计测试用例的时候,是通过一下代码来测试的----------------每次都会定义Solution类型的对象然后来调用,所以每一个测试用例就有一个vector< int>的重新定义,而不是像全局的vector< int>在整个main函数内使用的是同一个。
int main()
{vector<int> v;Solution s;v=s.reversePrint(phead1);//Print()Solution s;v=s.reversePrint(phead2);//Print()Solution s;v=s.reversePrint(phead3);//Print()return 0;
}