剑指 Offer 06. 从尾到头打印链表

剑指 Offer 06. 从尾到头打印链表

结果

第一种方法：

执行结果:通过显示详情
执行用时: 3 ms，在所有Java提交中击败了6.33%的用户

内存消耗:42.3MB，在所有Java提交中击败了12.17%的用户

通过测试用例:24/ 24

第二种方法

执行结果:通过显示详情>
执行用时:0 ms ,在所有Java提交中击败了100.00%的用户
内存消耗:41.8 MB ，在所有Java提交中击败了74.21%的用户
通过测试用例: 24/ 24

时间花费

10分钟

思路

• 第一种（自己实现的）

  根据ArrayList擅长查改、LinkedList擅长增删的特点，使用LinkedList每次都在最开始插入链接元素的值。最后将LinkedList转为int[]

  int[] a = ll.stream().mapToInt(Integet::valueof()).toArray();
  1

• 第二种(不仅简单，而且效果更好)

  先遍历链表得到size

  再遍历链表得到value，倒序填充链表

code1

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
        public int[] reversePrint(ListNode head) {
        /**
         * 考虑点：使用正确长度的数组
         *
         */
        if(head==null) return new int[0];
        LinkedList<Integer> ll = new LinkedList<>();
        while (head.next!=null ){
            ll.add(0,head.val);
            head = head.next;
        }
        ll.add(0,head.val);
        return ll.stream().mapToInt(Integer::valueOf).toArray();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

code2

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
       public int[] reversePrint(ListNode head) {
        //先获取链表长度，创建对应长度数组
        ListNode currNode = head;
        int len = 0;
        while(currNode != null){
            len ++;
            currNode = currNode.next;
        }
        int[] result = new int[len];
        
        //再次遍历链表，将值倒序填充至结果数组
        currNode = head;
        while(currNode != null){
            result[len - 1] = currNode.val;
            len --;
            currNode = currNode.next;
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29