单链表倒序
题目来源
牛客网
题目描述
- 输入一个链表,按链表从尾到头的顺序返回一个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;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)