题目:输入一个链表的头节点,从尾到头反过来打印出每个节点的值
解决方法:
- 使用 栈 (后进先出) ,遍历链表(从头到尾),输出是从尾到头
- 递归 (递归的本质也是一个栈结构)
- 头插法 (链表头插法为逆序)
代码实现:
/**
* 题目类型:链表
*
* 题目要求:输入一个链表的头节点,从尾到头反过来打印出每个节点的值
*
*思路:1. 遍历链表(从头到尾),输出是从尾到头,因此使用 栈 (后进先出)
*
* 2. 递归 (递归的本质也是一个栈结构)
*
* 3. 链表头插法(逆序)
*/
public class PrintLinkedList {
public static class ListNode {
private int value; // 节点的值
private ListNode next; // 下一个节点
}
/**
* 方式 1 :使用栈的方式
*
* @param root 头节点
*/
public static void printListFromTailToHead(ListNode root) {
Stack<ListNode> stack = new Stack<>();
while (root != null) {
stack.push(root);
root = root.next;
}
ListNode temp;
while (!stack.isEmpty()) {
temp = stack.pop();
System.out.print(temp.value + " ");
}
}
/**
* 方式 2 :递归
*
* @param root
*/
public static void printListByRecursion(ListNode root) {
if (root != null) {
printListByRecursion(root.next);
System.out.print(root.value + " ");
}
}
/**
* 方式 3 :头插法 (链表头插法为逆序) 尾插法为顺序
*
* 头节点和第一个节点的区别:
* 1. 头节点是在头插法中使用的一个额外节点,该节点不存储值
* 2. 第一个节点就是链表第一个真正存储值的节点
*
*时间复杂度:每个节点插入的时间为 O(1),设单链表长为 n,则 T(n) = O(n )
*
* @param root 原链表的头节点
*/
public static void printListByHeadInsertion(ListNode root) {
// 头插法构建逆序链表(新的链表的头节点)
ListNode head = new ListNode();
while (root != null) {
ListNode listNode = root.next; // listNode指向原链表的第二个节点
root.next = head.next; // 断开原链表头节点与其下一节点的连接
head.next = root; // 新链表的头结点的下一节点指向原链表的头节点
root = listNode;// 相当于 root = root.next
}
// 构建ArrayList
ArrayList<Integer> ret = new ArrayList<>();
head = head.next;
while (head != null) {
ret.add(head.value);
head = head.next;
}
for (int nodeValue : ret) {
System.out.print(nodeValue + " ");
}
}
public static void main(String[] args) {
ListNode root = new ListNode();
root.value = 1;
root.next = new ListNode();
root.next.value = 2;
root.next.next = new ListNode();
root.next.next.value = 3;
root.next.next.next = new ListNode();
root.next.next.next.value = 4;
root.next.next.next.next = new ListNode();
root.next.next.next.next.value = 5;
System.out.print("栈的方式:");
printListFromTailToHead(root);
System.out.println();
System.out.println();
System.out.print("递归(本质也是栈)的方式:");
printListByRecursion(root);
System.out.println();
System.out.println();
System.out.print("头插法的方式:");
printListByHeadInsertion(root);
}
}
网友评论