今日标题链接:从尾到头打印链表
从尾到头打印链表
难度：中等
描绘
输入一个链表的头节点，按链表从尾到头的次序回来每个节点的值（用数组回来）。
如输入{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;
}
}
}
