链接
https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
难度： #简单
题目
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
限制：
0 <= 链表长度 <= 10000
代码框架
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] reversePrint(ListNode head) {
}
}
题目解析
辅助思考图形：
[[06. 从尾到头打印链表.drawio]]
解答思路1：
递归遍历链表，
使用List保存链表的值，
深度优先遍历，
从链表的最后一个元素开始保存，
这样List保存的元素就是反转过的，
然后将List转换成数组返回即可。
解答思路2：
递归遍历链表，
使用全局变量保存计算过程的数据，
深度优先遍历，
到最后一个元素时，
能知道数组的大小，
然后从最后一个元素开始保存数据，
从数组的第一个元素开始保存，
直到回到链表的第一个元素反转完成。
解答思路3：
使用While循环正向遍历链表，
并将元素按照顺序保存在List中，
然后对List进行反转即可。
解答思路4：
使用While循环正向遍历链表，
计算出元素的总数，
然后申请对应大小的数组，
重新While循环正向遍历链表，
将遍历到的元素从数组的尾部开始插入，
实现链表的反转。
测试用例
package edu.yuwen.sowrd.num06.solution;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import edu.yuwen.sowrd.num06.ListNode;
import edu.yuwen.sowrd.num06.sol4.Solution;
public class SolutionTest {
/**
* 输入：head = [1,3,2]
* 输出：[2,3,1]
*/
@Test
public void testCase1() {
Solution solution = new Solution();
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(3);
ListNode node3 = new ListNode(2);
node1.next = node2;
node2.next = node3;
ListNode head = node1;
int[] res = solution.reversePrint(head);
Assertions.assertEquals(3, res.length);
Assertions.assertEquals(2, res[0]);
Assertions.assertEquals(3, res[1]);
Assertions.assertEquals(1, res[2]);
}
}
解答1
package edu.yuwen.sowrd.num06.sol1;
import java.util.ArrayList;
import java.util.List;
import edu.yuwen.sowrd.num06.ListNode;
public class Solution {
public int[] reversePrint(ListNode head) {
List<Integer> resList = new ArrayList<>();
recurve(head, resList);
int[] resArray = new int[resList.size()];
for (int i = 0; i < resList.size(); i++) {
resArray[i] = resList.get(i);
}
return resArray;
}
private void recurve(ListNode head, List<Integer> res) {
if (head == null) {
return;
}
recurve(head.next, res);
res.add(head.val);
}
}
解答2
package edu.yuwen.sowrd.num06.sol2;
import edu.yuwen.sowrd.num06.ListNode;
/**
* 解答思路2：
* 递归遍历链表，
* 使用全局变量保存计算过程的数据，
* 深度优先遍历，
* 到最后一个元素时，
* 能知道数组的大小，
* 然后从最后一个元素开始保存数据，
* 从数组的第一个元素开始保存，
* 直到回到链表的第一个元素反转完成。
*
*/
public class Solution {
// 保存返回结果的数组
int[] resArray;
// 数组的大小
int count;
// 数组当前的位置索引
int index;
public int[] reversePrint(ListNode head) {
if (head == null) {
return new int[0];
}
resArray = null;
count = 0;
index = 0;
recurve(head);
return resArray;
}
private void recurve(ListNode head) {
if (head.next == null) {
resArray = new int[count + 1];
// 找到最后一个结点，放到结果数组的第一个
resArray[0] = head.val;
return;
}
// 数组大小加1
count++;
// 遍历下一个元素
recurve(head.next);
// 索引向后移动一位，用于保存当前的元素
index++;
resArray[index] = head.val;
}
}
解答3
package edu.yuwen.sowrd.num06.sol3;
import java.util.ArrayList;
import java.util.List;
import edu.yuwen.sowrd.num06.ListNode;
/**
* 解答思路3：
* 使用While循环正向遍历链表，
* 并将元素按照顺序保存在List中，
* 然后对List进行反转即可。
*/
public class Solution {
public int[] reversePrint(ListNode head) {
if (head == null) {
return new int[0];
}
List<Integer> list = new ArrayList<>();
ListNode current = head;
while (current != null) {
// 先按照顺序保存
list.add(current.val);
// 移动到下一个结点
current = current.next;
}
// 反转List保存到返回数组中
int size = list.size();
int[] resArray = new int[size];
for (int i = 0; i < size; i++) {
// 从list中的最后一个开始保存，到结果数组的第一个
resArray[i] = list.get(size - 1 - i);
}
return resArray;
}
}
解答4 推荐
package edu.yuwen.sowrd.num06.sol4;
import edu.yuwen.sowrd.num06.ListNode;
/**
* 解答思路4：
* 使用While循环正向遍历链表，
* 计算出元素的总数，
* 然后申请对应大小的数组，
* 重新While循环正向遍历链表，
* 将遍历到的元素从数组的尾部开始插入，
* 实现链表的反转。
*/
public class Solution {
public int[] reversePrint(ListNode head) {
if (head == null) {
return new int[0];
}
// 计算链表的大小
int size = 0;
ListNode current = head;
while (current != null) {
size++;
// 移动到下一个结点
current = current.next;
}
int[] resArray = new int[size];
current = head;
for (int i = size - 1; i >= 0; i--) {
// 将遍历到的元素从数组的尾部开始插入
resArray[i] = current.val;
// 移动到下一个结点
current = current.next;
}
return resArray;
}
}
网友评论