【剑指Offer】6. 从尾到头打印链表

绝地灬酷狼 2023-03-06 03:54 10阅读 0赞

[NowCode][]

## 题目描述 ##

从尾到头反过来打印出每个结点的值。

## 解题思路 ##

### 使用递归 ###

要逆序打印链表 1->2->3（3,2,1)，可以先逆序打印链表 2->3(3,2)，最后再打印第一个节点 1。而链表 2->3 可以看成一个新的链表，要逆序打印该链表可以继续使用求解函数，也就是在求解函数中调用自己，这就是递归函数。

### 头插法 ###

使用头插法可以得到一个逆序的链表。

头结点和第一个节点的区别：

*  头结点是在头插法中使用的一个额外节点，这个节点不存储值；
 *  第一个节点就是链表的第一个真正存储值的节点。

/** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } * */
    import java.util.ArrayList;
    public class Solution { 
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { 
            // 头插法
            ListNode head = new ListNode(-1);
            while(listNode != null) { 
                ListNode temp = listNode.next;
                
                listNode.next = head.next;
                head.next = listNode;
                
                listNode = temp;
            }
            
            // 返回值
            ArrayList<Integer> re = new ArrayList<>();
            head = head.next;
            while(head != null) { 
                re.add(head.val);
                head = head.next;
            }
            
            return re;
        }       
    }

### 使用栈 ###

栈具有后进先出的特点，在遍历链表时将值按顺序放入栈中，最后出栈的顺序即为逆序。

/** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } * */
    import java.util.*;
    public class Solution { 
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { 
             Stack<Integer> stack = new Stack<>();
            while(listNode != null) { 
                stack.add(listNode.val);
                listNode = listNode.next;
            }
            
            // 返回值
            ArrayList<Integer> re = new ArrayList<>();
            while(!stack.isEmpty()) { 
                re.add(stack.pop());
            }
            
            return re;
        }       
    }

[NowCode]: https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&&tqId=11156&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking