Leetcode(剑指offer 06）

54 阅读 0 评论 36 点赞

我是靠谱客的博主魁梧钢笔，最近开发中收集的这篇文章主要介绍Leetcode(剑指offer 06），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

主要根据剑指 offer 怎么刷？ - 知乎

这个网站说的我来刷，目前准备记录一下每一个阶段刷的东西的一些方法和技巧。

开始：

这边看完题目的思路

将弄两个指针pre和cur，从前往后，实现反转链表，然后再将反转列表的值输入到数组中
~~弄个数组，按顺序存下来结果后，再建立一个新数组，反向存储。【长度未知，可以用arraylist】~~
弄个栈来实现先进后出的效果，栈中保存每个节点的val。

比较这三个思路，第一个反转链表需要遍历两次链表，加一个存储的数组。第二个思路遍历一次链表，加两个存储的数组。第三个思路需要遍历一次链表，一个栈，一个存储的数组。

如何选择的话，在我看来，主要看你怎么抉择空间复杂度和时间复杂度，针对思路一和思路三都写了代码，毕竟简单题，更多是考察对语法的熟悉程度。

这边代码就不细致写，只把一些需要注意的语法写一下就可以。

// 对stack的使用
// 1. 定义：
Stack <类别> stack = new Stack<类别>();

// 2. 往里面加东西,put 往外面弹东西，pop
stack.push(和上面类别相同的对象);
stack.pop();//返回值是一个对象；

// 3. 计算大小
size = stack.size();//计算大小

链表的话，就没啥好说的，记住反转链表的话，需要用pre和cur来存储，然后改变next指针的方向，这样写完之后，还能够把反转链表也给练了。反转链表的话，就挺简单，使用一个中间变量来存储cur指针的下一位，然后将cur指针的next指向pre。

 * 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 pre = new ListNode();
        ListNode cur = head;
        int num = 0;
        while(cur!=null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
            num+=1;
        }
        int [] a = new int[num]; 
        for(int i = 0;i<num;i++){
            a[i] = pre.val;
            pre = pre.next;
        }
        return a;
        

    }
}