每日一题《剑指offer》链表篇之从尾到头打印链表
从尾到头打印链表
难度：中等
描述
输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。
如输入{1,2,3}的链表如下图:
返回一个数组为[3,2,1]
数据范围
0 <= 链表长度 <= 10000
举例
解题思路
方法一：递归（推荐使用） 我们都知道链表无法逆序访问，那肯定无法直接遍历链表得到从尾到头的逆序结果。但是我们都知道递归是到达底层后才会往上回溯，因此我们可以考虑递归遍历链表，因此三段式如下：
- 终止条件： 递归进入链表尾，即节点为空节点时结束递归。
- 返回值： 每次返回子问题之后的全部输出。
- 本级任务： 每级子任务递归地进入下一级，等下一级的子问题输出数组返回时，将自己的节点值添加在数组末尾。
具体做法：
- step 1：从表头开始往后递归进入每一个节点。
- step 2：遇到尾节点后开始返回，每次返回依次添加一个值进入输出数组。
- step 3：直到递归返回表头。
方法二：栈（扩展思路） 递归的思想也可以用栈实现，因为栈是先进后出的，符合逆序的特点，递归本质上就是用栈实现的。
具体做法：
- step 1：我们可以顺序遍历链表，将链表的值push到栈中。
- step 2：然后再依次弹出栈中的元素，加入到数组中，即可实现链表逆序。
具体做法：
- step 1：我们可以顺序遍历链表，将链表的值push到栈中。
- step 2：然后再依次弹出栈中的元素，加入到数组中，即可实现链表逆序。
实现代码（java）
方法一
import java.util.ArrayList; public class Solution { //递归函数 public void recursion(ListNode head, ArrayList<Integer> res){ if(head != null){ //先往链表深处遍历 recursion(head.next, res); //再填充到数组就是逆序 res.add(head.val); } } public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> res = new ArrayList<Integer>(); //递归函数解决 recursion(listNode, res); return res; } }
方法二
import java.util.*; public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> res = new ArrayList<Integer>(); Stack<Integer> s = new Stack<Integer>(); //正序输出链表到栈中 while(listNode != null){ s.push(listNode.val); listNode = listNode.next; } //输出栈中元素到数组中 while(!s.isEmpty()) res.add(s.pop()); return res; } }
学习完本题的思路你可以解决如下题目：
从尾到头打印链表
难度：中等
描述
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
数据范围
数据范围： 0≤n≤1000
要求：空间复杂度 O(1) ，时间复杂度 O(n) 。
举例
解题思路
方法一：迭代 将链表反转，就是将每个表元的指针从向后变成向前，那我们可以遍历原始链表，将遇到的节点一一指针逆向即可。指针怎么逆向？不过就是断掉当前节点向后的指针，改为向前罢了。
| 1 | cur.next = pre |
具体做法：
- step 1：优先处理空链表，空链表不需要反转。
- step 2：我们可以设置两个指针，一个当前节点的指针，一个上一个节点的指针（初始为空）。
- step 3：遍历整个链表，每到一个节点，断开当前节点与后面节点的指针，并用临时变量记录后一个节点，然后当前节点指向上一个节点，即可以将指针逆向。
- step 4：再轮换当前指针与上一个指针，让它们进入下一个节点及下一个节点的前序节点。
方法二：递归 从上述方法一，我们可以看到每当我们反转链表的一个节点以后，要遍历进入下一个节点进入反转，相当于对后续的子链表进行反转，这可以看成是一个子问题，因此我们也可以使用递归，其三段式模版为：
- 终止条件： 当到达链表尾，要么当前指针是空，要么下一个指针是空，就返回。
- 返回值： 每一级返回反转后的子问题的头节点。
- 本级任务： 先进入后一个节点作为子问题。等到子问题都反转完成，再将本级节点与后一个的指针反转。
具体做法：
- step 1：对于每个节点我们递归向下遍历到最后的尾节点。
- step 2：然后往上依次逆转两个节点。
- step 3：将逆转后的本层节点，即反转后这后半段子链表的尾，指向null，返回最底层上来的头部节点。
实现代码（java）
方法一
public class Solution { public ListNode ReverseList(ListNode head) { //处理空链表 if(head == null) return null; ListNode cur = head; ListNode pre = null; while(cur != null){ //断开链表，要记录后续一个 ListNode temp = cur.next; //当前的next指向前一个 cur.next = pre; //前一个更新为当前 pre = cur; //当前更新为刚刚记录的后一个 cur = temp; } return pre; } }
方法二
public class Solution { public ListNode ReverseList(ListNode head) { //递归结束条件 if(head == null || head.next == null) return head; //反转下一个 ListNode newHead = ReverseList(head.next); //逆转本级节点 head.next.next = head; //尾部设置空节点 head.next = null; return newHead; } }
学习完本题的思路你可以解决如下题目：
合并两个排序的链表
难度：中等
描述
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围
数据范围： 0≤n≤1000，−1000≤节点值≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)
举例
解题思路
方法一：双指针迭代 这道题既然两个链表已经是排好序的，都是从小到大的顺序，那我们要将其组合，可以使用归并排序的思想：每次比较两个头部，从中取出最小的元素，然后依次往后。这样两个链表依次往后，我们肯定需要两个指针同方向访问才能实现。
具体过程：
- step 1：判断空链表的情况，只要有一个链表为空，那答案必定就是另一个链表了，就算另一个链表也为空。
- step 2：新建一个空的表头后面连接两个链表排序后的节点，两个指针分别指向两链表头。
- step 3：遍历两个链表都不为空的情况，取较小值添加在新的链表后面，每次只把被添加的链表的指针后移。
- step 4：遍历到最后肯定有一个链表还有剩余的节点，它们的值将大于前面所有的，直接连在新的链表后面即可。
方法二：双指针递归 上述方法一中，我们利用归并思想不断合并两个链表，每当我们添加完一个节点后，该节点指针后移，相当于这个链表剩余部分与另一个链表剩余部分合并，两个链表剩余部分合并就是原问题两个有序链表合并的子问题，因此也可以使用递归：
- 终止条件： 当一个链表已经因为递归到了末尾，另一个链表剩余部分一定都大于前面的，因此我们可以将另一个链表剩余部分拼在结果后面，结束递归。
- 返回值： 每次返回拼接好的较大部分的子链表。
- 本级任务： 每级不断进入下一个较小的值后的链表部分与另一个链表剩余部分，再将本次的节点接在后面较大值拼好的结果前面。
具体做法：
- step 1：每次比较两个链表当前节点的值，然后取较小值的链表指针往后，另一个不变，两段子链表作为新的链表送入递归中。
- step 2：递归回来的结果我们要加在当前较小值的节点后面，相当于不断在较小值后面添加节点。
- step 3：递归的终止是两个链表有一个为空。
实现代码（java）
方法一
public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { //一个已经为空了，直接返回另一个 if(list1 == null) return list2; if(list2 == null) return list1; //加一个表头 ListNode head = new ListNode(0); ListNode cur = head; //两个链表都要不为空 while(list1 != null && list2 != null){ //取较小值的节点 if(list1.val <= list2.val){ cur.next = list1; //只移动取值的指针 list1 = list1.next; }else{ cur.next = list2; //只移动取值的指针 list2 = list2.next; } //指针后移 cur = cur.next; } //哪个链表还有剩，直接连在后面 if(list1 != null) cur.next = list1; else cur.next = list2; //返回值去掉表头 return head.next; } }
方法二
public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { //一个已经为空了，返回另一个 if(list1 == null) return list2; if(list2 == null) return list1; //先用较小的值的节点 if(list1.val <= list2.val){ //递归往下 list1.next = Merge(list1.next, list2); return list1; }else{ //递归往下 list2.next = Merge(list1, list2.next); return list2; } } }
