得到单链表逆序遍历的结果

谁践踏了优雅 2022-11-30 01:43 110阅读 0赞

[https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking][https_www.nowcoder.com_practice_d0267f7f55b3412ba93bd35cfa8e8035_tpId_13_rp_1_ru_2Fta_2Fcoding-interviews_qru_2Fta_2Fcoding-interviews_2Fquestion-ranking]

**目录**

一、问题描述

二、代码实现

1、使用栈

2、采用头插法重新插入链表元素，将链表逆序（改动了输入的单链表）

3、直接递归获取逆序结果的写法（不改动输入的单链表）

--------------------

## 一、问题描述 ##

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

## 二、代码实现 ##

### 1、使用栈 ###

利用栈先进后出的特性：先从左到右遍历单链表，将所有元素添加到栈中；再将栈中所有元素弹出依次添加到ArrayList中。

/**
    *    public class ListNode {
    *        int val;
    *        ListNode next = null;
    *
    *        ListNode(int val) {
    *            this.val = val;
    *        }
    *    }
    *
    */
    import java.util.ArrayList;
    import java.util.Stack;
    public class Solution {
        
        public ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {
            if (listNode == null) {
                return new ArrayList<Integer>();
            }
            
            Stack<ListNode> stack = new Stack<>();
            ListNode cur = listNode;
            while (cur != null) {
                stack.push(cur);
                cur = cur.next;
            }
            
            ArrayList<Integer> result = new ArrayList<>();
            while (!stack.isEmpty()) {
                ListNode temp = stack.pop();
                result.add(temp.val);
            }
            
            return result;
        }
    }

### 2、采用头插法重新插入链表元素，将链表逆序（改动了输入的单链表） ###

先获取一个逆序后的单链表，再依次插入到ArrayList中。

import java.util.ArrayList;
    public class Solution {
        
        public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
            if (listNode == null) {
                return new ArrayList<Integer>();
            }
            
            listNode = reverse1(listNode);
            
            ArrayList<Integer> result = new ArrayList<>();
            ListNode cur = listNode;
            while (cur != null) {
                result.add(cur.val);
                cur = cur.next;
            }
            
            return result;   
        }
    
        //将输入的单链表改成逆序（采用头插法将单链表的所有元素重新插到新链表上）
        public static ListNode reverse1(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            
            ListNode newHead = null;
            while (head != null) {
                ListNode temp = head;
                head = head.next;
                
                temp.next = newHead;
                newHead = temp;
            }
            
            return newHead;
        }
        
    }

### 3、直接递归获取逆序结果的写法（不改动输入的单链表） ###

采用递归的写法，直接将逆序结果添加到ArrayList中。

import java.util.ArrayList;
    import java.util.Stack;
    public class Solution {
        static ArrayList<Integer> result = null;
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            if(listNode == null) {
                return new ArrayList<Integer>();
            }
            
            result = new ArrayList<>();    //避免存放两次的结果，由于这是个类变量，将reverse方法和result声明为非static也可以不这么写
            reverse(listNode);
            return result;
        }
    
        private static void reverse(ListNode head) {
            if (head.next != null) {
                reverse(head.next);
            }
            result.add(head.val);    //non-static variable result cannot be referenced from a static context
        }
        
    }

[https_www.nowcoder.com_practice_d0267f7f55b3412ba93bd35cfa8e8035_tpId_13_rp_1_ru_2Fta_2Fcoding-interviews_qru_2Fta_2Fcoding-interviews_2Fquestion-ranking]: https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking