🌕 剑指 Offer 06. 从尾到头打印链表
2022年10月10日
- algorithm
🌕 剑指 Offer 06. 从尾到头打印链表
难度: 🌕
问题描述
解法 1 - 递归反转链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
int len = 0;
public int[] reversePrint(ListNode head) {
// 思路:
// 递归反转链表
ListNode cur = mySol(null, head);
int[] res = new int[len];
for(int i = 0; i < len; i ++) {
res[i] = cur.val;
cur = cur.next;
}
return res;
}
private ListNode mySol(ListNode pre, ListNode cur) {
// 递归终止条件
if(cur == null) {
return pre;
}
// cur != null
len ++;
ListNode next = cur.next;
cur.next = pre;
return mySol(cur, next);
}
}
输出 1
解法 2 - 迭代反转链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
int len = 0;
public int[] reversePrint(ListNode head) {
// 思路:
// 先反转链表,同时记录元素个数,再顺序遍历
ListNode cur = mySol(head);
int[] res = new int[len];
int index = 0;
while(cur != null) {
res[index] = cur.val;
index ++;
cur = cur.next;
}
return res;
}
private ListNode mySol(ListNode head) {
if(head == null) {
return head;
}
ListNode pre = null;
ListNode cur = head;
while(cur != null) {
len ++;
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
输出 2
解法 3 - 顺序存入 List
/**
* 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
ArrayList<Integer> list = new ArrayList<>();
ListNode cur = head;
while(cur != null) {
list.add(cur.val);
cur = cur.next;
}
int len = list.size();
int[] res = new int[len];
for(int i = 0; i < len; i ++) {
res[i] = list.get(len - 1 - i);
}
return res;
}
}