Java实现方式
描述
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
代码
/** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } * */ import java.util.*; public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { /* //根据方法返回值类型，首先可以想到头插ArrayList的方法 ArrayList<Integer> list = new ArrayList<Integer>(); while(listNode != null){ list.add(0,listNode.val); listNode = listNode.next; } return list; */ /* //根据栈后进先出的特点实现 ArrayList<Integer> list = new ArrayList<Integer>(); Stack<Integer> stack = new Stack<Integer>(); while(listNode != null){ stack.push(listNode.val); listNode = listNode.next; } while(!stack.isEmpty()){ list.add(stack.pop()); } return list; */ //递归，每访问一个结点的时候，先递归输出它后面的结点 ArrayList<Integer> list = new ArrayList<Integer>(); if(listNode != null){ list = printListFromTailToHead(listNode.next); list.add(listNode.val); } return list; } }
C++实现方式
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) {
vector<int> v; //用来存放链表的值
//递归得到反转后的链表
ListNode* newHead = reverse(head);
//插入反转后的链表的值入数组v
ListNode* cur =newHead;
while(cur !=NULL){
v.push_back(cur->val);
cur = cur->next;
}
return v;
}
private:
//反转函数
ListNode* reverse(ListNode* head){
//如果链表为空或者只有一个结点，直接返回头指针
if(head == NULL || head->next == NULL){
return head;
}
//递归调用head->next后面的链表
ListNode* newHead = reverse(head->next);
//调整递归后的链表
//head->next->next是指向最后一个结点的指针
head->next->next = head;
//修改最后一个结点的指针为NULL
head->next = NULL;
//返回新的头结点
return newHead;
}
};
2.头插法实现思路及其实现代码
思路：
头插时候，先处理要头插数据的下一个结点，所以要保存将要头插结点的指针定义一个临时指针temp = head->next; 于此同时定义一个新指针 newHead = NULL;
处理将要头插的数据：即head = newHead;
处理头插前面的结点：newHead ->next = head;
处理结束后：旧头结点继续往前移动 head = temp;
开始插入数据入数组！
/**
* 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) {
vector<int> v;
ListNode* newHead = reverse(head);
ListNode* cur =newHead;
while(cur !=NULL){
v.push_back(cur->val);
cur = cur->next;
}
return v;
}
private:
ListNode* reverse(ListNode* head){
if(head == NULL || head->next == NULL){
return head;
}
ListNode* newHead = NULL;
//让头指针遍历链表进行头插
while(head !=NULL){
ListNode* temp = head->next;
head->next = newHead;
newHead = head;
head = temp;
}
return newHead;
}
};
3.栈模拟思路及其代码实现
思路：
由于栈的先进后出和这里的从尾打印链表刚好吻合，所以可以用栈来完成。
/**
* 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<int> stk;
vector<int> v;
//开始入栈
while(head != NULL){
stk.push(head->val);
//链表迭代往下走
head = head->next;
}
//开始出栈到数组
while(!stk.empty()){
v.push_back(stk.top());
stk.pop(); //记得弹栈
}
return v;
}
};
标签：head,ListNode,val,offer,next,链表,从尾,NULL From： https://www.cnblogs.com/sundayvc/p/16598190.html