单链表倒序

单链表倒序

题目来源

牛客网

题目描述

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。 public class ListNode { int val; ListNode next = null; public ListNode(int val) { this.val = val; } public void setNext(ListNode node) { this.next = node; } }

解题思路

考虑使用递归实现： 要实现 1->2->3->4->5 的倒序，那么首先要实现 2->3->4->5 的倒序 … 即实现5的倒序 import java.util.ArrayList; public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> list = new ArrayList<>(); if (listNode == null) { return list; } if (listNode.next != null) { list.addAll(printListFromTailToHead(listNode.next)); list.add(listNode.val); } else { list.add(listNode.val); } return list; } }

程序执行逻辑： 1->2->3->4->5进去方法中，首先不满足list.next != null 将listNode赋值为 2->3->4->5，然后将 2->3->4->5的倒序结果赋值给list保存, 2->3->4->5进去方法… 3->4->5… 4->5… 当5进入方法时由于listNode.next == null 所以list.add(5), 执行return list，结果赋值给了 4->5 倒序的方法，然后执行list.add(4)，list的结果变为了5,4 … 由此实现了单链表的倒序。

头插法：

由于链表的结构 只有val和next 两个属性，所以可以构造一个虚拟的节点，然后主链表遍历的时候将每次的节点赋值给头结点的next eg: 1->2->3->4->5倒序 构造一个虚拟节点-1 遍历1->2->3->4->5 将当前节点赋值给头结点的next -1->1 2->3->4->5 然后继续遍历 2->3->4->5 虚拟链表变为了 -1->2->1 主链表 3->4->5

直到主链表为null时遍历完毕。

import java.util.ArrayList; public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode{ // 头插法实现 首先创建一个虚拟节点 ArrayList<Integer> list = new ArrayList<>(); ListNode head = new ListNode(-1); while(listNode != null){ ListNode temp = listNode.next; listNode.next = head.next; head.next = listNode; listNode = temp; } head = head.next; while(head != null){ list.add(head.val); head = head.next; } return list; } } 利用栈先进后出的特性： import java.util.ArrayList; import java.util.Stack; public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> list = new ArrayList<>(); Stack<Integer> stack = new Stack<>(); while (listNode != null) { stack.push(listNode.val); listNode = listNode.next; } while (!stack.isEmpty()) { list.add(stack.pop()); } return list; } }