题目描述
输入一个链表,按链表从尾到头的顺序返回一个ArrayList。
题解一:递归
/*
在最后一次递归方法返回以后,每一层的递归方法都会做一个arrayList.add(listNode.val)这个操作,
从最后一次到第一次,逆向的调用了后面的方法
*/
static ArrayList<Integer> list = new ArrayList<>();
public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if (listNode != null) {
printListFromTailToHead(listNode.next);
list.add(listNode.val);
}
return list;
}
题解二:reverse()方法
public static ArrayList<Integer> printListFromTailToHead01(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;
}
节点结构定义
public static class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
从头插入节点
public static void insetFromHead(ListNode head,ListNode newNode){
newNode.next=head;
head = newNode;
}
在尾部插入节点
public static void insertFromTail(ListNode head, ListNode newNode){
//如果是个空链表,直接把新节点赋值给head,然后结束,要先判断null的情况
if(head == null){
head =newNode;
return;
}
//用temp代替head去遍历找到最后一个节点,一定不要用head自己去遍历,
ListNode temp = head;
while (temp.next!=null){
temp=temp.next;
}
temp.next=newNode;
}
计算链表的长度
public static int length(ListNode head){
int len =0;
ListNode temp = head;
while(temp!=null){
len++;
temp=temp.next;
}
return len;
}
按照顺序输出一个列表
public static void printList(ListNode head){
ListNode temp = head;
while(temp != null){
System.out.print(temp.val+" ");
temp = temp.next;
}
System.out.println();
}
从特定位置删除一个节点
public static boolean deleteFromIndex(ListNode head,int index){
if(index<1||index>length(head)){ //先判断是否越界
return false;
}
if(index ==1){//如果是删除第一个元素,因为直接涉及到了head所以只能单独处理
head = head.next;
return true;
}
ListNode curNode = head;
//删除顺序为index的node只能将curNode停在index-1的位置
for(int curIndex =1;curIndex<index-1;curIndex++){
curNode = curNode.next;
}
curNode.next=curNode.next.next;
return true;
}
测试:
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int nums = sc.nextInt();
ListNode headNode = new ListNode(1);
for(int i=2;i<=nums;i++){
insertFromTail(headNode,new ListNode(i));
}
printList(headNode);
ArrayList<Integer> list = printListFromTailToHead01(headNode);
System.out.println(list);
ArrayList<Integer> list1 = printListFromTailToHead(headNode);
System.out.println(list1);
deleteFromIndex(headNode,3);
printList(headNode);
int length = length(headNode);
System.out.println(length);
}
输入:8
输出:
1 2 3 4 5 6 7 8
[8, 7, 6, 5, 4, 3, 2, 1]
[8, 7, 6, 5, 4, 3, 2, 1]
1 2 4 5 6 7 8
7