进行做题之前,先来看看什么是ListNode。

ListNode是由自己定义的Java中的链表对象(其实也可以理解成C语言中的链表)。也就是在Java类库中没有这个类,需要自己定义。定义如下:

1
2
3
4
5
6
7
8
9
public class ListNode
{
int val;
ListNode next;

public ListNode(int x){
val=x;
}
}

val表示当前ListNode的值,next指向下一个ListNode。在进行ListNode初始化时必须传值,如下面main函数中进行初始化:

1
2
3
4
5
6
public static void main(String[] args) {
ListNode listNode = new ListNode(1);
listNode.next = new ListNode(3);
listNode.next.next = new ListNode(4);
listNode.next.next.next = new ListNode(1);
}

此时生成链表:1->3->4->1


题目描述:

1
输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。

方法一:利用栈的思想

一个链表从头到尾输入,要求输出的是从尾到头。符合栈先进后出的思想,因此可以用下面方法实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> stack = new Stack<Integer>();
while (listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}

ArrayList<Integer> arrayList = new ArrayList<Integer>();

while (!stack.isEmpty()) {
arrayList.add(stack.pop());
}

return arrayList;
}

方法二:递归

1
2
3
4
5
6
7
8
9
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> arrayList = new ArrayList<Integer>();
if (listNode != null) {
arrayList.addAll(printListFromTailToHead(listNode.next));
arrayList.add(listNode.val);
}
return arrayList;

}

顺便说一下addAll()和all()的区别:

add()是将传入的的参数作为当前 List 中d的一个项目(Item)来存储,即使你传入一个 list 也只会另当前的List集合增加 1 个元素。


addAll()是传入一个List,将此前List集合中的所有元素加入到当前的 List 中,当前 List 集合会增加的元素个数是传入的 List 的大小。

方法三:头插法

利用链表头插法为逆序的特点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> arrayList = new ArrayList<>();

ListNode head = new ListNode(-1);
while (listNode != null) {
ListNode q = listNode.next;
listNode.next = head.next;
head.next = listNode;
listNode = q;
}

head = head.next;
while (head != null) {
arrayList.add(head.val);
head = head.next;
}
return arrayList;
}

方法四:链表翻转

  • 利用函数:
1
2
3
4
5
6
7
8
9
10
11
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<Integer>();

while(listNode != null){
list.add(listNode.val);
listNode = listNode.next;
}

Collections.reverse(list);//使用Collections的reverse方法,直接将list反转
return list;
}
  • 强行进行逆序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> arr = new ArrayList<Integer>();
if(listNode == null){
return arr;
}
while(listNode.next != null){
arr.add(listNode.val);
listNode = listNode.next;
}
arr.add(listNode.val);
int temp = 0;
for(int inx=0, end=arr.size()-1; inx<end; inx++, end--){
temp = arr.get(inx);
arr.set(inx, arr.get(end));
arr.set(end, temp);
}
return arr;
}