题目描述
输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。
解题思路(Java)
1)利用栈来实现;
2)用Collections集合类;
3)利用三个指针把链表反转,关键是 r 指针保存断开的节点;
4)借助递归实现(递归的本质还是使用了堆栈结构)
- 统一定义:
/**
* 定义一个ListNode类
* @author 章鱼宝宝
*
*/
class ListNode{
int val; //数据域
ListNode next = null; //指针域
public ListNode(int val) {
this.val=val;
}
}
- 1)利用栈来实现
public class Demo01 {
public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> stack = new Stack<Integer>();
ArrayList<Integer> list = new ArrayList<Integer>();
while(listNode!=null) {
stack.push(listNode.val);
listNode=listNode.next;
}
while(!stack.isEmpty()) {
list.add(stack.pop());
}
return list;
}
}
- 2)用Collections集合类
public class Demo01 {
public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<Integer>();
while(listNode!=null) {
list.add(listNode.val);
listNode=listNode.next;
}
Collections.reverse(list);
return list;
}
}
- 3)利用三个指针把链表反转,关键是 r 指针保存断开的节点
public class Demo01 {
public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode == null)
return new ArrayList<Integer>();
ListNode head = listNode;
ListNode cur = listNode.next;
while(cur!= null){
ListNode temp = cur.next;
cur.next = head;
head = cur;
cur = temp;
}
//此时listNode的next还指向第二个node,所以要让listNode.next=null,防止循环
listNode.next = null;
ArrayList<Integer> res = new ArrayList<Integer>();
while(head !=null){
res.add(head.val);
head = head.next;
}
return res;
}
}
- 4)借助递归实现(递归的本质还是使用了堆栈结构)
public class Demo01 {
public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list=new ArrayList<Integer>();
ListNode pNode=listNode;
if(pNode!=null){
if(pNode.next!=null){
list=printListFromTailToHead(pNode.next);
}
list.add(pNode.val);
}
return list;
}
}
- 测试主方法
public static void main(String[] args) {
ListNode listNode = new ListNode(1);
ListNode listNode2 = new ListNode(2);
ListNode listNode3 = new ListNode(3);
ListNode listNode4 = new ListNode(4);
listNode3.next = listNode4;
listNode2.next = listNode3;
listNode.next = listNode2;
System.out.println(printListFromTailToHead(listNode));
}
网友评论