VIRTUALS

the virtual labs for the virtuals

0%

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

Posted on Edited on In , , ,

摘要：
考察链表遍历，递归一波带走。

题目

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入： head = [1,3,2]
输出： [2,3,1]

限制：

$ 0 <= 链表长度 <= 10000 $

链表定义：

1
2
3
4
5
6
7
8
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
1
2
3
4
5
6
7
8
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

递归（系统栈）

递归遍历链表，“归（回溯）”的时候输出节点值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 执行用时: 8 ms
// 内存消耗: 9 MB
class Solution {
public:
    vector<int> res;
    vector<int> reversePrint(ListNode* head) {
        dfs(head);
        return res;
    }

    void dfs(ListNode* head) {
        if (!head) return;
        dfs(head->next);
        res.push_back(head->val);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 执行用时: 1 ms
// 内存消耗: 39.4 MB
class Solution {
    List<Integer> list;
    int len;
    public int[] reversePrint(ListNode head) {
        list = new ArrayList<>();
        dfs(head);

        len = list.size();
        int[] res = new int[len];

        for (int i = 0; i < len; i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    void dfs(ListNode head) {
        if (head == null) return;
        dfs(head.next);
        list.add(head.val);
    }
}

栈

利用栈的特性。注意Java语言中的栈结构一般用LinkedList.
LinkedList<Integer> stk = new LinkedList<>();
涉及到的方法有：
addLast()对应 push, removeLast()对应 pop, size().

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 执行用时: 4 ms
// 内存消耗: 8.7 MB
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> res;
        
        stack<int> stk;
        for (; head; head = head->next) {
            stk.push(head->val);
        }

        for (; !stk.empty(); stk.pop()) {
            res.push_back(stk.top());
        }

        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 执行用时: 1 ms
// 内存消耗: 39.3 MB
class Solution {
    public int[] reversePrint(ListNode head) {
        LinkedList<Integer> stk = new LinkedList<>();

        for (; head != null; head = head.next) {
            stk.addLast(head.val);
        }

        int len = stk.size();
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            res[i] = stk.removeLast();
        }

        return res;
    }
}

模拟栈

当你忘了STL或者java的sdk api中的栈怎么用的时候，就模拟栈吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 执行用时: 8 ms
// 内存消耗: 8.5 MB
class Solution {
public:
    int stk[10010], tt = 0;
    vector<int> reversePrint(ListNode* head) {
        vector<int> res;
        for (; head; head = head->next) {
            stk[++tt] = head->val;      // push
        }

        for (; tt;) {
            res.push_back(stk[tt--]);
        }

        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 执行用时: 1 ms
// 内存消耗: 38.4 MB
class Solution {
    public int[] reversePrint(ListNode head) {
        int[] stk = new int[10010];
        int tt = 0;
        for (; head != null; head = head.next) {
            stk[++tt] = head.val;
        }

        int[] res = new int[tt];
        for (int i = 0; tt > 0; i++, tt--) {
            res[i] = stk[tt];
        }

        return res;
    }
}

原题链接： 剑指Offer 06. 从尾到头打印链表