23张图！万字详解「链表」，从小白到大佬！

 链表和数组是数据类型中两个重要又常用的基础数据类型。

成都创新互联公司是一家朝气蓬勃的网站建设公司。公司专注于为企业提供信息化建设解决方案。从事网站开发，网站制作，网站设计，网站模板，微信公众号开发，软件开发，小程序开发，10年建站对宣传片制作等多个行业，拥有多年的网站推广经验。

数组是连续存储在内存中的数据结构，因此它的优势是可以通过下标迅速的找到元素的位置，而它的缺点则是在插入和删除元素时会导致大量元素的被迫移动，为了解决和平衡此问题于是就有了链表这种数据类型。

链表和数组可以形成有效的互补，这样我们就可以根据不同的业务场景选择对应的数据类型了。那么，本文我们就来重点介绍学习一下链表，一是因为它非常重要，二是因为面试必考，先来看本文大纲：

看过某些抗日神剧我们都知道，某些秘密组织为了防止组织的成员被“一窝端”，通常会采用上下级单线联系的方式来保护其他成员，而这种“行为”则是链表的主要特征。

简介

链表(Linked List)是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

链表是由数据域和指针域两部分组成的，它的组成结构如下：

复杂度分析

由于链表无需按顺序存储，因此链表在插入的时可以达到 O(1) 的复杂度，比顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间，而顺序表插入和查询的时间复杂度分别是 O(log n) 和 O(1)。

优缺点分析

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

分类

链表通常会分为以下三类：

  • 单向链表
  • 双向链表
  • 循环链表
  • 单循链表
  • 双循环链表

1.单向链表

链表中最简单的一种是单向链表，或叫单链表，它包含两个域，一个数据域和一个指针域，指针域用于指向下一个节点，而最后一个节点则指向一个空值，如下图所示：

单链表的遍历方向单一，只能从链头一直遍历到链尾。它的缺点是当要查询某一个节点的前一个节点时，只能再次从头进行遍历查询，因此效率比较低，而双向链表的出现恰好解决了这个问题。

接下来，我们用代码来实现一下单向链表的节点：

 
 
 
 
    
  
  
  
  
  1. private static class Node {
    2. 
  
  
  
  
  2.     E item;
    3. 
  
  
  
  
  3.     Node next;
    4. 
  
  
  
  
  4. 
  
  
  
  
  5.     Node(E element, Node next) {
    6. 
  
  
  
  
  6.         this.item = element;
    7. 
  
  
  
  
  7.         this.next = next;
    8. 
  
  
  
  
  8.     }
    9. 
  
  
  
  
  9. }
    10.

2.双向链表

双向链表也叫双面链表，它的每个节点由三部分组成：prev 指针指向前置节点，此节点的数据和 next 指针指向后置节点，如下图所示：

接下来，我们用代码来实现一下双向链表的节点：

 
 
 
 
    
  
  
  
  
  1. private static class Node {
    2. 
  
  
  
  
  2.     E item;
    3. 
  
  
  
  
  3.     Node next;
    4. 
  
  
  
  
  4.     Node prev;
    5. 
  
  
  
  
  5. 
  
  
  
  
  6.     Node(Node prev, E element, Node next) {
    7. 
  
  
  
  
  7.         this.item = element;
    8. 
  
  
  
  
  8.         this.next = next;
    9. 
  
  
  
  
  9.         this.prev = prev;
    10. 
  
  
  
  
  10.     }
    11. 
  
  
  
  
  11. }
    12.

3.循环链表

循环链表又分为单循环链表和双循环链表，也就是将单向链表或双向链表的首尾节点进行连接，这样就实现了单循环链表或双循环链表了，如下图所示：

Java中的链表

学习了链表的基础知识之后，我们来思考一个问题：Java 中的链表 LinkedList 是属于哪种类型的链表呢?单向链表还是双向链表?

要回答这个问题，首先我们要来看 JDK 中的源码，如下所示：

 
 
 
 
    
  
  
  
  
  1. package java.util;
    2. 
  
  
  
  
  2. 
  
  
  
  
  3. import java.util.function.Consumer;
    4. 
  
  
  
  
  4. 
  
  
  
  
  5. public class LinkedList
    6. 
  
  
  
  
  6.     extends AbstractSequentialList
    7. 
  
  
  
  
  7.     implements List, Deque, Cloneable, java.io.Serializable
    8. 
  
  
  
  
  8. {
    9. 
  
  
  
  
  9.  // 链表大小
    10. 
  
  
  
  
  10.     transient int size = 0;
    11. 
  
  
  
  
  11. 
  
  
  
  
  12.     // 链表头部
    13. 
  
  
  
  
  13.     transient Node first;
    14. 
  
  
  
  
  14. 
  
  
  
  
  15.     // 链表尾部
    16. 
  
  
  
  
  16.     transient Node last;
    17. 
  
  
  
  
  17. 
  
  
  
  
  18.     public LinkedList() {
    19. 
  
  
  
  
  19.     }
    20. 
  
  
  
  
  20. 
  
  
  
  
  21.     public LinkedList(Collection c) {
    22. 
  
  
  
  
  22.         this();
    23. 
  
  
  
  
  23.         addAll(c);
    24. 
  
  
  
  
  24.     }
    25. 
  
  
  
  
  25.  
    26. 
  
  
  
  
  26.     // 获取头部元素
    27. 
  
  
  
  
  27.     public E getFirst() {
    28. 
  
  
  
  
  28.         final Node f = first;
    29. 
  
  
  
  
  29.         if (f == null)
    30. 
  
  
  
  
  30.             throw new NoSuchElementException();
    31. 
  
  
  
  
  31.         return f.item;
    32. 
  
  
  
  
  32.     }
    33. 
  
  
  
  
  33. 
  
  
  
  
  34.     // 获取尾部元素
    35. 
  
  
  
  
  35.     public E getLast() {
    36. 
  
  
  
  
  36.         final Node l = last;
    37. 
  
  
  
  
  37.         if (l == null)
    38. 
  
  
  
  
  38.             throw new NoSuchElementException();
    39. 
  
  
  
  
  39.         return l.item;
    40. 
  
  
  
  
  40.     }
    41. 
  
  
  
  
  41. 
  
  
  
  
  42.     // 删除头部元素
    43. 
  
  
  
  
  43.     public E removeFirst() {
    44. 
  
  
  
  
  44.         final Node f = first;
    45. 
  
  
  
  
  45.         if (f == null)
    46. 
  
  
  
  
  46.             throw new NoSuchElementException();
    47. 
  
  
  
  
  47.         return unlinkFirst(f);
    48. 
  
  
  
  
  48.     }
    49. 
  
  
  
  
  49. 
  
  
  
  
  50.     // 删除尾部元素
    51. 
  
  
  
  
  51.     public E removeLast() {
    52. 
  
  
  
  
  52.         final Node l = last;
    53. 
  
  
  
  
  53.         if (l == null)
    54. 
  
  
  
  
  54.             throw new NoSuchElementException();
    55. 
  
  
  
  
  55.         return unlinkLast(l);
    56. 
  
  
  
  
  56.     }
    57. 
  
  
  
  
  57. 
  
  
  
  
  58.     // 添加头部元素
    59. 
  
  
  
  
  59.     public void addFirst(E e) {
    60. 
  
  
  
  
  60.         linkFirst(e);
    61. 
  
  
  
  
  61.     }
    62. 
  
  
  
  
  62.     
    63. 
  
  
  
  
  63.     // 添加头部元素的具体执行方法
    64. 
  
  
  
  
  64.     private void linkFirst(E e) {
    65. 
  
  
  
  
  65.         final Node f = first;
    66. 
  
  
  
  
  66.         final Node newNode = new Node<>(null, e, f);
    67. 
  
  
  
  
  67.         first = newNode;
    68. 
  
  
  
  
  68.         if (f == null)
    69. 
  
  
  
  
  69.             last = newNode;
    70. 
  
  
  
  
  70.         else
    71. 
  
  
  
  
  71.             f.prev = newNode;
    72. 
  
  
  
  
  72.         size++;
    73. 
  
  
  
  
  73.         modCount++;
    74. 
  
  
  
  
  74.     }
    75. 
  
  
  
  
  75. 
  
  
  
  
  76.     // 添加尾部元素
    77. 
  
  
  
  
  77.     public void addLast(E e) {
    78. 
  
  
  
  
  78.         linkLast(e);
    79. 
  
  
  
  
  79.     }
    80. 
  
  
  
  
  80.     
    81. 
  
  
  
  
  81.     // 添加尾部元素的具体方法
    82. 
  
  
  
  
  82.     void linkLast(E e) {
    83. 
  
  
  
  
  83.         final Node l = last;
    84. 
  
  
  
  
  84.         final Node newNode = new Node<>(l, e, null);
    85. 
  
  
  
  
  85.         last = newNode;
    86. 
  
  
  
  
  86.         if (l == null)
    87. 
  
  
  
  
  87.             first = newNode;
    88. 
  
  
  
  
  88.         else
    89. 
  
  
  
  
  89.             l.next = newNode;
    90. 
  
  
  
  
  90.         size++;
    91. 
  
  
  
  
  91.         modCount++;
    92. 
  
  
  
  
  92.     }
    93. 
  
  
  
  
  93. 
  
  
  
  
  94.     // 查询链表个数
    95. 
  
  
  
  
  95.     public int size() {
    96. 
  
  
  
  
  96.         return size;
    97. 
  
  
  
  
  97.     }
    98. 
  
  
  
  
  98. 
  
  
  
  
  99.     // 清空链表
    100. 
  
  
  
  
  100.     public void clear() {
    101. 
  
  
  
  
  101.         for (Node x = first; x != null; ) {
    102. 
  
  
  
  
  102.             Node next = x.next;
    103. 
  
  
  
  
  103.             x.item = null;
    104. 
  
  
  
  
  104.             x.next = null;
    105. 
  
  
  
  
  105.             x.prev = null;
    106. 
  
  
  
  
  106.             x = next;
    107. 
  
  
  
  
  107.         }
    108. 
  
  
  
  
  108.         first = last = null;
    109. 
  
  
  
  
  109.         size = 0;
    110. 
  
  
  
  
  110.         modCount++;
    111. 
  
  
  
  
  111.     }
    112. 
  
  
  
  
  112.   
    113. 
  
  
  
  
  113.     // 根据下标获取元素
    114. 
  
  
  
  
  114.     public E get(int index) {
    115. 
  
  
  
  
  115.         checkElementIndex(index);
    116. 
  
  
  
  
  116.         return node(index).item;
    117. 
  
  
  
  
  117.     }
    118. 
  
  
  
  
  118. 
  
  
  
  
  119.     private static class Node {
    120. 
  
  
  
  
  120.         E item;
    121. 
  
  
  
  
  121.         Node next;
    122. 
  
  
  
  
  122.         Node prev;
    123. 
  
  
  
  
  123. 
  
  
  
  
  124.         Node(Node prev, E element, Node next) {
    125. 
  
  
  
  
  125.             this.item = element;
    126. 
  
  
  
  
  126.             this.next = next;
    127. 
  
  
  
  
  127.             this.prev = prev;
    128. 
  
  
  
  
  128.         }
    129. 
  
  
  
  
  129.     }
    130. 
  
  
  
  
  130.     // 忽略其他方法......
    131. 
  
  
  
  
  131. }
    132.

从上述节点 Node 的定义可以看出：LinkedList 其实是一个双向链表，因为它定义了两个指针 next 和 prev 分别用来指向自己的下一个和上一个节点。

链表常用方法

LinkedList 的设计还是很巧妙的，了解了它的实现代码之后，下面我们来看看它是如何使用的?或者说它的常用方法有哪些。

1.增加

接下来我们来演示一下增加方法的使用：

 
 
 
 
    
  
  
  
  
  1. public class LinkedListTest {
    2. 
  
  
  
  
  2.     public static void main(String[] a) {
    3. 
  
  
  
  
  3.         LinkedList list = new LinkedList();
    4. 
  
  
  
  
  4.         list.add("Java");
    5. 
  
  
  
  
  5.         list.add("中文");
    6. 
  
  
  
  
  6.         list.add("社群");
    7. 
  
  
  
  
  7.         list.addFirst("头部添加"); // 添加元素到头部
    8. 
  
  
  
  
  8.         list.addLast("尾部添加");  // 添加元素到最后
    9. 
  
  
  
  
  9.         System.out.println(list);
    10. 
  
  
  
  
  10.     }
    11. 
  
  
  
  
  11. }
    12.

以上代码的执行结果为：

  • [头部添加, Java, 中文, 社群, 尾部添加]

出来以上的 3 个增加方法之外，LinkedList 还包含了其他的添加方法，如下所示：

  • add(int index, E element)：向指定位置插入元素;
  • offer(E e)：向链表末尾添加元素，返回是否成功;
  • offerFirst(E e)：头部插入元素，返回是否成功;
  • offerLast(E e)：尾部插入元素，返回是否成功。

add 和 offer 的区别

它们的区别主要体现在以下两点：

offer 方法属于 Deque接口，add 方法属于 Collection的接口;

当队列添加失败时，如果使用 add 方法会报错，而 offer 方法会返回 false。

2.删除

删除功能的演示代码如下：

 
 
 
 
    
  
  
  
  
  1. import java.util.LinkedList;
    2. 
  
  
  
  
  2. 
  
  
  
  
  3. public class LinkedListTest {
    4. 
  
  
  
  
  4.     public static void main(String[] a) {
    5. 
  
  
  
  
  5.         LinkedList list = new LinkedList();
    6. 
  
  
  
  
  6.         list.offer("头部");
    7. 
  
  
  
  
  7.         list.offer("中间");
    8. 
  
  
  
  
  8.         list.offer("尾部");
    9. 
  
  
  
  
  9. 
  
  
  
  
  10.         list.removeFirst(); // 删除头部元素
    11. 
  
  
  
  
  11.         list.removeLast();  // 删除尾部元素
    12. 
  
  
  
  
  12. 
  
  
  
  
  13.         System.out.println(list);
    14. 
  
  
  
  
  14.     }
    15. 
  
  
  
  
  15. }
    16.

以上代码的执行结果为：

[中间]

除了以上删除方法之外，更多的删除方法如下所示：

  • clear()：清空链表;
  • removeFirst()：删除并返回第一个元素;
  • removeLast()：删除并返回最后一个元素;
  • remove(Object o)：删除某一元素，返回是否成功;
  • remove(int index)：删除指定位置的元素;
  • poll()：删除并返回第一个元素;
  • remove()：删除并返回第一个元素。

3.修改

修改方法的演示代码如下：

 
 
 
 
    
  
  
  
  
  1. import java.util.LinkedList;
    2. 
  
  
  
  
  2. 
  
  
  
  
  3. public class LinkedListTest {
    4. 
  
  
  
  
  4.     public static void main(String[] a) {
    5. 
  
  
  
  
  5.         LinkedList list = new LinkedList();
    6. 
  
  
  
  
  6.         list.offer("Java");
    7. 
  
  
  
  
  7.         list.offer("MySQL");
    8. 
  
  
  
  
  8.         list.offer("DB");
    9. 
  
  
  
  
  9.         
    10. 
  
  
  
  
  10.         // 修改
    11. 
  
  
  
  
  11.         list.set(2, "Oracle");
    12. 
  
  
  
  
  12. 
  
  
  
  
  13.         System.out.println(list);
    14. 
  
  
  
  
  14.     }
    15. 
  
  
  
  
  15. }
    16.

以上代码的执行结果为：

 
 
 
 
    
  
  
  
  
  1. [Java, MySQL, Oracle]
    2.

4.查询查询方法的演示代码如下：

 
 
 
 
    
  
  
  
  
  1. import java.util.LinkedList;
    2. 
  
  
  
  
  2. 
  
  
  
  
  3. public class LinkedListTest {
    4. 
  
  
  
  
  4.     public static void main(String[] a) {
    5. 
  
  
  
  
  5.         LinkedList list = new LinkedList();
    6. 
  
  
  
  
  6.         list.offer("Java");
    7. 
  
  
  
  
  7.         list.offer("MySQL");
    8. 
  
  
  
  
  8.         list.offer("DB");
    9. 
  
  
  
  
  9. 
  
  
  
  
  10.         // --- getXXX() 获取 ---
    11. 
  
  
  
  
  11.         // 获取最后一个
    12. 
  
  
  
  
  12.         System.out.println(list.getLast());
    13. 
  
  
  
  
  13.         // 获取首个
    14. 
  
  
  
  
  14.         System.out.println(list.getFirst());
    15. 
  
  
  
  
  15.         // 根据下标获取
    16. 
  
  
  
  
  16.         System.out.println(list.get(1));
    17. 
  
  
  
  
  17. 
  
  
  
  
  18.         // peekXXX() 获取
    19. 
  
  
  
  
  19.         System.out.println("--- peek() ---");
    20. 
  
  
  
  
  20.         // 获取最后一个
    21. 
  
  
  
  
  21.         System.out.println(list.peekLast());
    22. 
  
  
  
  
  22.         // 获取首个
    23. 
  
  
  
  
  23.         System.out.println(list.peekFirst());
    24. 
  
  
  
  
  24.         // 根据首个
    25. 
  
  
  
  
  25.         System.out.println(list.peek());
    26. 
  
  
  
  
  26.     }
    27. 
  
  
  
  
  27. }
    28.

以上代码的执行结果为：

 
 
 
 
    
  
  
  
  
  1. DB
    2. 
  
  
  
  
  2. 
  
  
  
  
  3. Java
    4. 
  
  
  
  
  4. 
  
  
  
  
  5. MySQL
    6. 
  
  
  
  
  6. 
  
  
  
  
  7. --- peek() ---
    8. 
  
  
  
  
  8. 
  
  
  
  
  9. DB
    10. 
  
  
  
  
  10. 
  
  
  
  
  11. Java
    12. 
  
  
  
  
  12. 
  
  
  
  
  13. Java
    14.

5.遍历

LinkedList 的遍历方法包含以下三种。

遍历方法一：

 
 
 
 
    
  
  
  
  
  1. for (int size = linkedList.size(), i = 0; i < size; i++) {
    2. 
  
  
  
  
  2.     System.out.println(linkedList.get(i));
    3. 
  
  
  
  
  3. }
    4.

遍历方法二：

 
 
 
 
    
  
  
  
  
  1. for (String str: linkedList) {
    2. 
  
  
  
  
  2.     System.out.println(str);
    3. 
  
  
  
  
  3. }
    4.

遍历方法三：

 
 
 
 
    
  
  
  
  
  1. Iterator iter = linkedList.iterator();
    2. 
  
  
  
  
  2. while (iter.hasNext()) {
    3. 
  
  
  
  
  3.     System.out.println(iter.next());
    4. 
  
  
  
  
  4. }
    5.

链表应用：队列 & 栈

1.用链表实现栈

接下来我们用链表来实现一个先进先出的“队列”，实现代码如下：

 
 
 
 
    
  
  
  
  
  1. LinkedList list = new LinkedList();
    2. 
  
  
  
  
  2. // 元素入列
    3. 
  
  
  
  
  3. list.add("Java");
    4. 
  
  
  
  
  4. list.add("中文");
    5. 
  
  
  
  
  5. list.add("社群");
    6. 
  
  
  
  
  6. 
  
  
  
  
  7. while (!list.isEmpty()) {
    8. 
  
  
  
  
  8.     // 打印并移除队头元素
    9. 
  
  
  
  
  9.     System.out.println(list.poll());
    10. 
  
  
  
  
  10. }
    11.

以上程序的执行结果如下：

  • Java
  • 中文
  • 社群

2.用链表实现队列

然后我们用链表来实现一个后进先出的“栈”，实现代码如下：

 
 
 
 
    
  
  
  
  
  1. LinkedList list = new LinkedList();
    2. 
  
  
  
  
  2. // 元素入栈
    3. 
  
  
  
  
  3. list.add("Java");
    4. 
  
  
  
  
  4. list.add("中文");
    5. 
  
  
  
  
  5. list.add("社群");
    6. 
  
  
  
  
  6. 
  
  
  
  
  7. while (!list.isEmpty()) {
    8. 
  
  
  
  
  8.     // 打印并移除栈顶元素
    9. 
  
  
  
  
  9.     System.out.println(list.pollLast());
    10. 
  
  
  
  
  10. }
    11.

以上程序的执行结果如下：

  • 社群
  • 中文
  • Java

链表使用场景

链表作为一种基本的物理结构，常被用来构建许多其它的逻辑结构，如堆栈、队列都可以基于链表实现。

所谓的物理结构是指可以将数据存储在物理空间中，比如数组和链表都属于物理数据结构;而逻辑结构则是用于描述数据间的逻辑关系的，它可以由多种不同的物理结构来实现，比如队列和栈都属于逻辑结构。

链表常见笔试题

链表最常见的笔试题就是链表的反转了，之前的文章《链表反转的两种实现方法，后一种击败了100%的用户!》我们提供了 2 种链表反转的方法，而本文我们再来扩充一下，提供 3 种链表反转的方法。

实现方法 1：Stack我们先用图解的方式来演示一下，使用栈实现链表反转的具体过程，如下图所示。

全部入栈：

全部入栈：

因为栈是先进后出的数据结构，因此它的执行过程如下图所示：

最终的执行结果如下图所示：

实现代码如下所示：

 
 
 
 
    
  
  
  
  
  1. public ListNode reverseList(ListNode head) {
    2. 
  
  
  
  
  2.     if (head == null) return null;
    3. 
  
  
  
  
  3.     Stack stack = new Stack<>();
    4. 
  
  
  
  
  4.     stack.push(head); // 存入第一个节点
    5. 
  
  
  
  
  5.     while (head.next != null) {
    6. 
  
  
  
  
  6.         stack.push(head.next); // 存入其他节点
    7. 
  
  
  
  
  7.         head = head.next; // 指针移动的下一位
    8. 
  
  
  
  
  8.     }
    9. 
  
  
  
  
  9.     // 反转链表
    10. 
  
  
  
  
  10.     ListNode listNode = stack.pop(); // 反转第一个元素
    11. 
  
  
  
  
  11.     ListNode lastNode = listNode; // 临时节点，在下面的 while 中记录上一个节点
    12. 
  
  
  
  
  12.     while (!stack.isEmpty()) {
    13. 
  
  
  
  
  13.         ListNode item = stack.pop(); // 当前节点
    14. 
  
  
  
  
  14.         lastNode.next = item;
    15. 
  
  
  
  
  15.         lastNode = item;
    16. 
  
  
  
  
  16.     }
    17. 
  
  
  
  
  17.     lastNode.next = null; // 最后一个节点赋为null（不然会造成死循环）
    18. 
  
  
  
  
  18.     return listNode;
    19. 
  
  
  
  
  19. }
    20.

LeetCode 验证结果如下图所示：

可以看出使用栈的方式来实现链表的反转执行的效率比较低。

实现方法2：递归

同样的，我们先用图解的方式来演示一下，此方法实现的具体过程，如下图所示。

实现代码如下所示：

 
 
 
 
    
  
  
  
  
  1. public static ListNode reverseList(ListNode head) {
    2. 
  
  
  
  
  2.     if (head == null || head.next == null) return head;
    3. 
  
  
  
  
  3.     // 从下一个节点开始递归
    4. 
  
  
  
  
  4.     ListNode reverse = reverseList(head.next);
    5. 
  
  
  
  
  5.     head.next.next = head; // 设置下一个节点的 next 为当前节点
    6. 
  
  
  
  
  6.     head.next = null; // 把当前节点的 next 赋值为 null，避免循环引用
    7. 
  
  
  
  
  7.     return reverse;
    8. 
  
  
  
  
  8. }
    9.

LeetCode 验证结果如下图所示：

可以看出这种实现方法在执行效率方面已经满足我们的需求了，性能还是很高的。

实现方法 3：循环

我们也可以通过循环的方式来实现链表反转，只是这种方法无需重复调用自身方法，只需要一个循环就搞定了，实现代码如下：

 
 
 
 
    
  
  
  
  
  1. class Solution {
    2. 
  
  
  
  
  2.     public ListNode reverseList(ListNode head) {
    3. 
  
  
  
  
  3.         if (head == null) return null;
    4. 
  
  
  
  
  4.         // 最终排序的倒序链表
    5. 
  
  
  
  
  5.         ListNode prev = null;
    6. 
  
  
  
  
  6.         while (head != null) {
    7. 
  
  
  
  
  7.             // 循环的下个节点
    8. 
  
  
  
  
  8.             ListNode next = head.next;
    9. 
  
  
  
  
  9.             // 反转节点操作
    10. 
  
  
  
  
  10.             head.next = prev;
    11. 
  
  
  
  
  11.             // 存储下个节点的上个节点
    12. 
  
  
  
  
  12.             prev = head;
    13. 
  
  
  
  
  13.             // 移动指针到下一个循环
    14. 
  
  
  
  
  14.             head = next;
    15. 
  
  
  
  
  15.         }
    16. 
  
  
  
  
  16.         return prev;
    17. 
  
  
  
  
  17.     }
    18. 
  
  
  
  
  18. }
    19.

LeetCode 验证结果如下图所示：

从上述图片可以看出，使用此方法在时间复杂度和空间复杂度上都是目前的最优解，比之前的两种方法更加理想。

总结

本文我们讲了链表的定义，它是由数据域和指针域两部分组成的。链表可分为：单向链表、双向链表和循环链表，其中循环链表又可以分为单循链表和双循环链表。通过 JDK 的源码可知，Java 中的 LinkedList 其实是双向链表，我们可以使用它来实现队列或者栈，最后我们讲了反转链表的 3 种实现方法，希望本文的内容对你有帮助。

新闻标题：23张图！万字详解「链表」，从小白到大佬！
本文网址：http://www.gawzjz.com/qtweb/news23/190373.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

定制网站知识

分类信息网站

大英网站建设　　 　温江做网站　　 　梓潼网站制作公司　　 　网站建设开发　　 　成都app开发　　 　香港服务器空间　　 　什邡网站建设　　 　网站空间　　 　微信公众号开发　　 　节能环保网站建设方案　　 　企业网站建设公司　　 　网页改版　　 　成都网站设计　　 　成都网站建设流程　　 　绵阳服务器托管　　 　马边网站建设　　 　成都微信公众号开发　　 　网站设计制作报价　　 　遂宁网站建设　　 　四川和正源