链表应用：队列 & 栈
1.用链表实现栈
接下来我们用链表来实现一个先进先出的“队列”，实现代码如下：
LinkedList list = new LinkedList(); // 元素入列 list.add("Java"); list.add("中文"); list.add("社群"); while (!list.isEmpty()) { // 打印并移除队头元素 System.out.println(list.poll()); }
以上程序的执行结果如下：
Java
中文
社群
2.用链表实现队列
然后我们用链表来实现一个后进先出的“栈”，实现代码如下：
LinkedList list = new LinkedList(); // 元素入栈 list.add("Java"); list.add("中文"); list.add("社群"); while (!list.isEmpty()) { // 打印并移除栈顶元素 System.out.println(list.pollLast()); }
以上程序的执行结果如下：
社群
中文
Java
链表使用场景
链表作为一种基本的物理结构，常被用来构建许多其它的逻辑结构，如堆栈、队列都可以基于链表实现。
所谓的物理结构是指可以将数据存储在物理空间中，比如数组和链表都属于物理数据结构；而逻辑结构则是用于描述数据间的逻辑关系的，它可以由多种不同的物理结构来实现，比如队列和栈都属于逻辑结构。
链表常见笔试题
链表最常见的笔试题就是链表的反转了，之前的文章《链表反转的两种实现方法，后一种击败了100%的用户！》我们提供了 2 种链表反转的方法，而本文我们再来扩充一下，提供 3 种链表反转的方法。
实现方法 1：Stack
我们先用图解的方式来演示一下，使用栈实现链表反转的具体过程，如下图所示。
全部入栈：
因为栈是先进后出的数据结构，因此它的执行过程如下图所示：
最终的执行结果如下图所示：
实现代码如下所示：
public ListNode reverseList(ListNode head) { if (head == null) return null; Stack<ListNode> stack = new Stack<>(); stack.push(head); // 存入第一个节点 while (head.next != null) { stack.push(head.next); // 存入其他节点 head = head.next; // 指针移动的下一位 } // 反转链表 ListNode listNode = stack.pop(); // 反转第一个元素 ListNode lastNode = listNode; // 临时节点，在下面的 while 中记录上一个节点 while (!stack.isEmpty()) { ListNode item = stack.pop(); // 当前节点 lastNode.next = item; lastNode = item; } lastNode.next = null; // 最后一个节点赋为null（不然会造成死循环） return listNode; }
LeetCode 验证结果如下图所示：
可以看出使用栈的方式来实现链表的反转执行的效率比较低。
实现方法 2：递归
同样的，我们先用图解的方式来演示一下，此方法实现的具体过程，如下图所示。
实现代码如下所示：
public static ListNode reverseList(ListNode head) { if (head == null || head.next == null) return head; // 从下一个节点开始递归 ListNode reverse = reverseList(head.next); head.next.next = head; // 设置下一个节点的 next 为当前节点 head.next = null; // 把当前节点的 next 赋值为 null，避免循环引用 return reverse; }
LeetCode 验证结果如下图所示：
可以看出这种实现方法在执行效率方面已经满足我们的需求了，性能还是很高的。
实现方法 3：循环
我们也可以通过循环的方式来实现链表反转，只是这种方法无需重复调用自身方法，只需要一个循环就搞定了，实现代码如下：
class Solution { public ListNode reverseList(ListNode head) { if (head == null) return null; // 最终排序的倒序链表 ListNode prev = null; while (head != null) { // 循环的下个节点 ListNode next = head.next; // 反转节点操作 head.next = prev; // 存储下个节点的上个节点 prev = head; // 移动指针到下一个循环 head = next; } return prev; } }
LeetCode 验证结果如下图所示：
从上述图片可以看出，使用此方法在时间复杂度和空间复杂度上都是目前的最优解，比之前的两种方法更加理想。
总结
本文我们讲了链表的定义，它是由数据域和指针域两部分组成的。链表可分为：单向链表、双向链表和循环链表，其中循环链表又可以分为单循链表和双循环链表。通过 JDK 的源码可知，Java 中的 LinkedList 其实是双向链表，我们可以使用它来实现队列或者栈，最后我们讲了反转链表的 3 种实现方法，希望本文的内容对你有帮助。
