今日标题链接:从尾到头打印链表

从尾到头打印链表

难度：中等

描绘

输入一个链表的头节点，按链表从尾到头的次序回来每个节点的值（用数组回来）。

如输入{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;
    }
}

学习完本题的思路你能够处理如下标题：

JZ24. 回转链表

从尾到头打印链表

难度：中等

描绘

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，回转该链表后，回来新链表的表头。

数据规模

数据规模： 0≤n≤1000

要求：空间复杂度 O(1) ，时刻复杂度 O(n) 。

举例

解题思路

办法一：迭代 将链表回转，便是将每个表元的指针从向后变成向前，那咱们能够遍历原始链表，将遇到的节点一一指针逆向即可。指针怎么逆向？不过便是断掉当时节点向后的指针，改为向前罢了。

详细做法：

• 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;
        }
    }
}