剑指 Offer 06. 从尾到头打印链表-跟着帅地玩转校招，拿捏大厂offerPlayOffer

本问题对应的 leetcode 原文链接：剑指 Offer 06. 从尾到头打印链表

问题描述

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

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

限制：

0 <= 链表长度 <= 10000

代码实现

    // 从右边=往左填充
    public int[] reversePrint(ListNode head) {
        if(head == null)
            return new int[0];
        // 统计链表节点个数，方便创建数组
        int count = 0;
        ListNode temp = head;
        while(temp != null){
            count++;
            temp = temp.next;
        }
        int[] res = new int[count];
        int k = count - 1;
        // 从由往左填充数组
        while(head != null){
            res[k--] = head.val;
            head = head.next;
        }

        return res;
    }

时间复杂度：O(n)
额外空间复杂度：O(1)

Python

# 从右边往左填充
class Solution(object):
    def reversePrint(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        if not head:
            return []

        # 统计链表节点个数，方便创建数组
        count = 0
        temp = head
        while temp:
            count += 1
            temp = temp.next

        res = [0] * count
        k = count - 1
        # 从右往左填充数组
        while head:
            res[k] = head.val
            k -= 1
            head = head.next

        return res

C++

// 从右边往左填充
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        if(!head)
            return {};

        // 统计链表节点个数，方便创建数组
        int count = 0;
        ListNode* temp = head;
        while(temp){
            count++;
            temp = temp->next;
        }

        vector<int> res(count);
        int k = count - 1;
        // 从右往左填充数组
        while(head){
            res[k--] = head->val;
            head = head->next;
        }

        return res;
    }
};

Go

// 从右边往左填充
func reversePrint(head *ListNode) []int {
    if head == nil {
        return []int{}
    }

    // 统计链表节点个数，方便创建数组
    count := 0
    temp := head
    for temp != nil {
        count++
        temp = temp.Next
    }

    res := make([]int, count)
    k := count - 1
    // 从右往左填充数组
    for head != nil {
        res[k] = head.Val
        k--
        head = head.Next
    }

    return res
}

JS

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var reversePrint = function(head) {
    if(head == null)
        return new Array(0);
    // 统计链表节点个数，方便创建数组
    let count = 0;
    let temp = head;
    while(temp != null){
        count++;
        temp = temp.next;
    }
    let res = new Array(count);
    let k = count - 1;
    // 从右往左填充数组
    while(head != null){
        res[k--] = head.val;
        head = head.next;
    }

    return res;
};

剑指offer题解

发表回复取消回复

后才能评论

H、普通 2023年7月8日下午4:28

时间O(n)，空间O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();

        if(head == null){
            return new int[] { };
        }

        if(head.next == null){
            return new int[] {head.val};
        }

        ListNode temp = head;
        int nodeCount = 0;
        while (temp.next != null){
            temp = temp.next;
            nodeCount++;
        }

        int[] result = new int[nodeCount+1];

        while (head != null){
            result[nodeCount] = head.val;
            head = head.next;
            nodeCount--;
        }

        return result;

    }


}

杨帆普通 2022年11月1日下午4:29

public int[] reversePrint(ListNode head) {
int len = 0;
ListNode cur = head;
while(cur != null){
cur = cur.next;
len++;
}
int[] a = new int[len];
int num = 1;
cur = head;
while(cur != null){
a[len-num] = cur.val;
num++;
cur = cur.next;
}
return a;
}

时间复杂度：O(n)
额外空间复杂度：O(1)

登录以回复

lobort 普通 2022年10月26日下午7:06

class Solution {
public int[] reversePrint(ListNode head) {
//方法一 创建指针遍历得到链表的长度 新建一个数组 从尾开始增加链表的值 注意数组的长度和元素的下表不要出错！！
if(head == null){
return new int[0];
}
int count = 0;
ListNode temp = head;
while(temp!=null){
temp = temp.next;
count++;
}
int [] res = new int[count];
int k = count -1;
while(head!=null){
res[k–] = head.val;
head = head.next;
}
return res;


//方法二：利用栈先进后处的特点来完成 stack.add()增加元素 stack.pop()弹出栈内最上面的元素
Stack st = new Stack();
int count = 0;
while(head!=null){
st.add(head.val);
head = head.next;
}
int [] res = new int[st.size()];
for(int i =0; i <res.length; i++){
res[i] = st.pop();
}
return res;
}
}

lobort 普通 2022年10月26日下午7:05

“`java
class Solution {
public int[] reversePrint(ListNode head) {
//方法一创建指针遍历得到链表的长度新建一个数组从尾开始增加链表的值注意数组的长度和元素的下表不要出错！！
if(head == null){
return new int[0];
}
int count = 0;
ListNode temp = head;
while(temp!=null){
temp = temp.next;
count++;
}
int [] res = new int[count];
int k = count -1;
while(head!=null){
res[k–] = head.val;
head = head.next;
}
return res;

//方法二：利用栈先进后处的特点来完成 stack.add()增加元素 stack.pop()弹出栈内最上面的元素
Stack st = new Stack();
int count = 0;
while(head!=null){
st.add(head.val);
head = head.next;
}
int [] res = new int[st.size()];
for(int i =0; i <res.length; i++){
res[i] = st.pop();
}
return res;
}
}

登录以回复

cxc 普通 2022年10月24日下午11:55

class Solution {
    List<Integer> list = new ArrayList();
    public int[] reversePrint(ListNode head) {
        recur(head);
        int[] res = new int[list.size()];
        for(int i=0;i<res.length;i++){
            res[i] = list.get(i);
        }

        return res;
    }

    public void recur(ListNode head) {
        if(head == null) return;
        recur(head.next);
        //递归的时候添加到list头
        list.add(head.val);
    }
}

zjl 普通 2022年10月24日下午7:14

递归。但是list怎么能直接取出数组？

    public int[] reversePrint(ListNode head) {
        List<Integer> list = new ArrayList();
        addNode(head,list);
        int[] arr = new int[list.size()];
        for(int i = 0 ; i < arr.length;i++){
            arr[i] = list.get(i);
        }
        return arr;

    }
    public void addNode(ListNode node , List<Integer> list){
        if(node==null){
            return;
        }
        addNode(node.next,list);
        list.add(node.val);
    }

🚲南下普通 2022年10月24日上午10:37

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        int counter = 0; //之前忘记赋初值
        ListNode* pre = head;
        while(pre!=nullptr){
            counter++;
            pre = pre->next;
        }

        vector<int> A(counter); //定义数组接收
        while(head!=nullptr){
            // A.push_back(head->val);
            A[counter-1] = head->val; //从后往前赋值
            head=head->next;
            counter--;
        }
        return A;

    }
};

Edison 普通 2022年10月23日下午9:32

思路一：先反转链表，再遍历，这样就不需要额外的栈空间开销

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        //先反转链表，再遍历，这样就不需要额外的栈空间开销
        vector<int> ret;

        // 空链表
        if (head == nullptr) {
            return ret;
        }

        // 反转链表
        ListNode* cur = head->next;
        ListNode* temp;
        head->next = nullptr;
        while (cur) { // 遍历链表
            temp = cur->next;
            cur->next = head;
            head = cur;
            cur = temp;
        }

        // 直接尾插
        while (head) {
            ret.push_back(head->val);
            head = head->next;
        }
        // 返回ret数组
        return ret;
    }
};

方法二：使用栈

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> ret;
        stack<int> st;
        while (head) {
            st.push(head->val); //把链表元素全部放入栈中
            head = head->next;
        }
        while (!st.empty()) {
            ret.push_back(st.top()); // 把栈顶元素放到ret数组中
            st.pop();
        }
        return ret;
    }
};

方法三：就地逆序数组

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> ret;

        // 把链表所有元素尾插到ret数组中
        while (head) {
            ret.push_back(head->val);
            head = head->next;
        }
        int len = ret.size(); //统计元素个数

        // 交换第一个和最后一个，只需要交换len/2次
        for (int i = 0; i < len / 2; ++i) {
            swap(ret[i], ret[len-i-1]);
        }
        return ret;
    }
};

问题描述

代码实现

Python

C++

Go

JS

发表回复 取消回复

评论(8)

发表回复取消回复