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

算法系统课免费

课后作业

问题描述

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

示例 1：

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

限制：

0 <= 链表长度 <= 10000

代码实现

Java

/**
 * 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];
        }

        int n = 0;
        ListNode temp = head;
        while(temp != null){
            n++;
            temp = temp.next;
        }
        int res[] = new int[n];
        while(head != null){
            res[--n] = head.val;
            head = head.next;
        }

        return res;

    }
}

Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reversePrint(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        if head == None:
            return []

        n = 0
        temp = head
        while temp != None:
            n += 1
            temp = temp.next
        res = [0]*n
        while head != None:
            n -= 1
            res[n] = head.val
            head = head.next

        return res

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        if (head == NULL) {
            return vector<int>();
        }

        int n = 0;
        ListNode* temp = head;
        while (temp != NULL) {
            n++;
            temp = temp->next;
        }

        vector<int> res(n);
        while (head != NULL) {
            n--;
            res[n] = head->val;
            head = head->next;
        }

        return res;
    }
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reversePrint(head *ListNode) []int {
    if head == nil {
        return []int{}
    }

    n := 0
    temp := head
    for temp != nil {
        n++
        temp = temp.Next
    }

    res := make([]int, n)
    for head != nil {
        n--
        res[n] = head.Val
        head = head.Next
    }

    return res
}

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: # 递归 def reverseBookList(self, head: Optional[ListNode]) -> List[int]: return self.reverseBookList(head.next) + [head.val] if head else []

class Solution: def reverseBookList(self, head: ListNode) -> List[int]: stack = [] while head: stack.append(head.val) head = head.next return stack[::-1]

class Solution { //打卡 public int[] reverseBookList(ListNode head) { if(head == null ){ return new int[0]; } int n = 0; ListNode cur = head; while(cur != null){ n++; cur = cur.next; } int[] res = new int[n]; cur = head; for(int i = n-1;i >=0;i--){ res[i] = cur.val; cur =cur.next; } return res; } }

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ // 【思路】用栈，后进先出 class Solution { public int[] reversePrint(ListNode head) { Stack<Integer> s = new Stack<Integer>(); int i = 0; while(head != null) { s.push(head.val); head = head.next; i++; } int[] ans = new int[i]; for(int j = 0; j < i; j++) { ans[j] = s.pop(); } return ans; } }

class Solution { public: void reverse(ListNode* head, vector<int> &res) { if(head == nullptr) return; reverse(head->next, res); res.push_back(head->val); } vector<int> reversePrint(ListNode* head) { if(head == nullptr) return vector<int>(); vector<int> res; reverse(head, res); return res; } };

//递归 //时间复杂度O(n) //空间复杂度O(n) class Solution { ArrayList list = new ArrayList<>(); public int[] reversePrint(ListNode head) { if(head == null) return new int[0]; print(head); int[] res = new int[list.size()]; for(int i = 0; i < list.size(); i++){ res[i] = list.get(i); } return res; } public void print(ListNode head){ if(head == null) return; print(head.next); list.add(head.val); } } //栈 class Solution { public int[] reversePrint(ListNode head) { Stack stack = new Stack(); ListNode temp = head; while (temp != null) { stack.push(temp); temp = temp.next; } int size = stack.size(); int[] print = new int[size]; for (int i = 0; i < size; i++) { print[i] = stack.pop().val; } return print; } }

class Solution { public: vector<int> reversePrint(ListNode* head) { // 把链表元素倒着放在向量里 vector<int> a; if(!head) { return a; } if(!head->next) { a.push_back(head->val); return a; } //先把head->next的链表倒着放在向量里 a = reversePrint(head->next); //在把head->next放在最后 a.push_back(head->val); return a; } };

class Solution { public int[] reversePrint(ListNode head) { if(head == null){ return new int[0]; } int n = 0; ListNode temp = head; while(temp != null){ n++; temp = temp.next; } int res[] = new int[n]; while(head != null){ res[--n] = head.val; head = head.next; } return res; } }

发表回复取消回复

后才能评论

我来吃饭啦永久会员 2024年6月18日下午7:43

Mr.肖永久会员 2024年3月25日下午10:34

Yuki 永久会员 2024年1月28日上午10:44
可以写出，不计入打卡
class Solution {
public:
vector reverseBookList(ListNode* head) {
stackst;
vectorres;
int tmp=0;
if(headnullptr)return res;
ListNode*cur=head;
```
    while(cur!=nullptr){
        st.push(cur->val);
        cur=cur->next;
    }
    while(!st.empty()){
        tmp=st.top();
        res.push_back(tmp);
        st.pop();
    }
    return res;
}
```
};
登录以回复

uu 永久会员 2023年9月19日下午5:17

Thaddeus 永久会员 2023年8月30日下午2:40

递归

阿尚普通 2023年8月17日上午11:05

纸飞机永久会员 2023年8月8日下午11:30

3_🔥 永久会员 2023年7月9日下午10:28

记录个数，然后从后往前给数组赋值即可

帅气的冬瓜普通 2023年6月27日下午5:32

打卡

登录以回复

课后作业

问题描述

代码实现

Java

Python

C++

Go

发表回复 取消回复

评论(9)

递归

付款后无法显示下载地址或者无法查看内容？

发表回复取消回复