链表

概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的 逻辑顺序 是通过链表中的 引用链接 次序实现的 。

如下图，每一个方框代表一个结点，每一个结点分为数据域与引用域，每个结点的数据域存储数据，引用域则存放下一个结点的引用，各个结点通过引用连接起来，通过下图也可以观察到：每个结点的地址一般是跳跃式的，不一定是连续的，这也是链表与顺序表的区别之一。

链表的种类多种多样，分为带头或不带头、单向或双向、循环或不循环，组合起来共有8种：

• 带头链表，即会创建一个额外的结点，这个结点的引用域引用链表实际的第一个结点，而数据域无意义，通过头结点就可以访问到整个链表
• 双向链表，即每个结点会存在两个引用域，一个引用下一个结点，一个引用上一个结点，对于第一个结点，它没有上一个结点（不带头）所以为null
• 循环链表，最后一个结点的引用域不为null，而是引用第一个结点，如此达到循环的效果

虽然链表的结构有8种，但是我们重点掌握两种结构：

• 不带头单向不循环链表： 简称单链表，结构简单，一般不会单独存放数据，一般作为其他数据结构的子结构，如哈希桶、图的邻接表等。但实现操作的代码较困难复杂，许多的题目都是围绕这种结构
• 不带头双向链表： Java集合框架的LinkedList的底层就是一个双向链表

---

单链表的实现

实现一个单链表，并实现基本的操作。首先，我们得有结点，即结点对象，实现一个结点类。

如下代码，外部类为MySingleList，将结点类ListNode作为静态内部类，其包含两个成员变量，分别是数据域val和引用域next（它将引用下一个结点对象），并给出构造方法。其次，为了方便操作，我们再定义一个成员变量head，存放链表的第一个结点的地址。

public class MySingleList implements IList {//结点内部类static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}//链表的第一个结点public ListNode head;//重写的方法
}

实现了我们自定义的IList接口，所以必须重写方法，数据结构一定要多画图！建议结合下面的代码好好画图！

public interface IList {//头插法public void addFirst(int data);//尾插法public void addLast(int data);//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中public boolean contains(int key);//删除第一次出现关键字为key的节点public void remove(int key);//删除所有值为key的节点public void removeAllKey(int key);//得到单链表的长度public int size();//清空public void clear();//打印public void display();
}

---

public void display()

先从最简单的打印入手，假设我们已经有一个链表，并且已经有第一个结点的引用head

思路：利用结点的引用域不断向后遍历链表并打印数据

    //打印链表元素@Overridepublic void display() {//临时变量，避免修改成员变量headListNode cur = this.head;//为null停下while(cur != null) {System.out.print(cur.val + " ");cur = cur.next;//向后寻找}System.out.println();//手动换行}

---

public int size()

思路：定义一个计数器，遍历链表，不断计数

    //链表结点数@Overridepublic int size() {int count = 0;ListNode cur = this.head;while(cur != null) {count++;cur = cur.next;}return count;}

---

public void clear()

清空有"暴力"清空和非暴力清空，"暴力清空"只需要head == null;即可，这里我们给出非暴力清空，即将每个结点的next均置为null并将head置为null

    //清空@Overridepublic void clear() {ListNode cur = head;while (cur != null) {ListNode curN = cur.next;cur.next = null;cur = curN;}head = null;}

---

public void addFirst(int data)

头插即将新的结点插入到链表的头部，使其成为链表新的头部

• 必须申请一个新的结点对象
• 考虑链表为空的情况，即head == null

    //头插@Overridepublic void addFirst(int data) {//实例化一个结点对象ListNode newNode = new ListNode(data);//链表为空if(this.head == null) {this.head = newNode;return;}//链表不为空newNode.next = head;head = newNode;}

---

public void addLast(int data)

尾插即将新结点插入到链表结尾，使其成为新的尾结点

• 考虑链表为空的情况
• 想要尾插，必须找到最后一个结点，让它的next指向新的结点，按照之前的循环条件cur != null，cur会走到null，所以我们改变循环条件为cur.next != null，这样就能保证cur最后指向尾结点

如此我们有：

• 如果想遍历链表的每个结点，循环条件为cur != null
• 如果想找到尾结点，循环条件为cur.next != null

    //尾插@Overridepublic void addLast(int data) {//实例化一个结点对象ListNode newNode = new ListNode(data);//链表为空if(this.head == null) {this.head = newNode;return;}//链表不为空ListNode cur = this.head;while(cur.next != null) {cur = cur.next;}cur.next = newNode;}

---

public void addIndex(int index,int data)

任意位置插入，前提：假设第一个结点的位置为0，以此类推，在指定位置插入新结点。

思路：必须找到原链表指定位置的前一个结点，让它的next指向新结点，并将新结点的next指向原结点。

• 这里我们自定义了一个异常，“下标非法异常”

  public class IllegalIndexException extends RuntimeException {public IllegalIndexException(String message) {super(message);}
  }
  

  • 我们采用了让cur循环结束时停留在指定位置结点的前一个结点的位置，这样我们就可以拿到所需的所有结点，注意这里的语句顺序，必须先让新结点的next指向原来的指定位置结点，然后再让原指定位置结点的前一个结点指向新结点。

    //指定位置插入,假设第一个结点标记为0位置@Overridepublic void addIndex(int index, int data) {//非法下标，抛出自定义异常if(index < 0 || index > size()) {throw new IllegalIndexException("Illegal Index !:下标非法");}//插入位置为0，相当于头插if(index == 0) {addFirst(data);return;}//寻找指定下标的前一个结点，方便更改链表的指向ListNode newNode = new ListNode(data);ListNode cur = this.head;for(int i = 0; i < index - 1; i++) {cur = cur.next;}//注意语句顺序newNode.next = cur.next;cur.next = newNode;}

---

public boolean contains(int key)

• 链表为空，肯定不包含任何结点
• 不为空，遍历寻找即可

    //检查是否包含某个元素@Overridepublic boolean contains(int key) {if(this.head == null) {return false;}ListNode cur = this.head;while(cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}

---

public void remove(int key)

删除结点，要让它的前一个结点的next指向它的后一个结点

• 自定义了一个异常：“链表为空的异常”，空链表无法删除（看个人喜好）
• 情况一：第一个结点就为待删除结点
• 情况二：情况一之外，代码会直接从第二个结点开始判断，所以我们事先判断是否为情况一

    //删除第一个指定的数据@Overridepublic void remove(int key) {if(this.head == null) {throw new ListIsEmptyException("The SingleList is Empty!: 链表为空！");}//第一个结点满足if(head.val == key) {head = head.next;return;}//遍历寻找并删除ListNode cur = this.head;while(cur.next != null) {if(cur.next.val == key) {cur.next = cur.next.next;break;}cur = cur.next;}}

---

public void removeAllKey(int key)

这个方法考虑的事情很多，代码一开始判断是否为空链表，然后跳过第一个结点向后寻找待删除的结点，方法是：定义两个引用，一个是寻找引用cur，它负责向后寻找待删除结点，另一个prev是为了执行删除操作，改变它的指向。

• 当cur指向的结点不满足条件，则两个引用均向后一位（注意语句顺序）

• 当cur指向的结点满足条件，则prev不动，让prev指向cur的下一个结点，删除成功，然后cur向后一位。

  为什么prev不动呢？ 为了解决多个待删除的结点连续的情况

最后，判断第一个结点是否为待删除结点，执行操作。

    //删除全部的指定数据@Overridepublic void removeAllKey(int key) {if(this.head == null) {throw new ListIsEmptyException("The SingleList is Empty!: 链表为空！");}//先删除所有第一个结点后面的指定结点ListNode prev = this.head;ListNode cur = prev.next;while(cur != null) {if(cur.val == key) {prev.next = cur.next;}else {prev = cur;}cur = cur.next;}//最后检查第一个结点是否满足删除条件if(this.head.val == key) {head = head.next;}}

---

完整实现如下（接口和异常类不额外再给出了）：

public class MySingleList implements IList {//结点内部类static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}//链表的第一个结点public ListNode head;//头插@Overridepublic void addFirst(int data) {//实例化一个结点对象ListNode newNode = new ListNode(data);//链表为空if(this.head == null) {this.head = newNode;return;}//链表不为空newNode.next = head;head = newNode;}//尾插@Overridepublic void addLast(int data) {//实例化一个结点对象ListNode newNode = new ListNode(data);//链表为空if(this.head == null) {this.head = newNode;return;}//链表不为空ListNode cur = this.head;while(cur.next != null) {cur = cur.next;}cur.next = newNode;}//指定位置插入,假设第一个结点标记为0位置@Overridepublic void addIndex(int index, int data) {//非法下标，抛出自定义异常if(index < 0 || index > size()) {throw new IllegalIndexException("Illegal Index !:下标非法");}//插入位置为0，相当于头插if(index == 0) {addFirst(data);return;}//寻找指定下标的前一个结点，方便更改链表的指向ListNode newNode = new ListNode(data);ListNode cur = this.head;for(int i = 0; i < index - 1; i++) {cur = cur.next;}newNode.next = cur.next;cur.next = newNode;}//检查是否包含某个元素@Overridepublic boolean contains(int key) {if(this.head == null) {return false;}ListNode cur = this.head;while(cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}//删除第一个指定的数据@Overridepublic void remove(int key) {if(this.head == null) {throw new ListIsEmptyException("The SingleList is Empty!: 链表为空！");}//第一个结点满足if(head.val == key) {head = head.next;return;}//遍历寻找并删除ListNode cur = this.head;while(cur.next != null) {if(cur.next.val == key) {cur.next = cur.next.next;break;}cur = cur.next;}}//删除全部的指定数据@Overridepublic void removeAllKey(int key) {if(this.head == null) {throw new ListIsEmptyException("The SingleList is Empty!: 链表为空！");}//先删除所有第一个结点后面的指定结点ListNode prev = this.head;ListNode cur = prev.next;while(cur != null) {if(cur.val == key) {prev.next = cur.next;}else {prev = cur;}cur = cur.next;}//最后检查第一个结点是否满足删除条件if(this.head.val == key) {head = head.next;}}//链表结点数@Overridepublic int size() {int count = 0;ListNode cur = this.head;while(cur != null) {count++;cur = cur.next;}return count;}//清空@Overridepublic void clear() {ListNode cur = head;while (cur != null) {ListNode curN = cur.next;cur.next = null;cur = curN;}head = null;}//打印链表元素@Overridepublic void display() {ListNode cur = this.head;while(cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}
}

实现完单链表后，就可以跳转到相关练习部分，练习相关题目

---

LinkedList的使用

LinkedList是Java集合框架中的一个类，底层实现是一个双向链表，其实现了List接口，其在集合框架中的位置如下：

• LinkedList没有实现RandomAccess接口，因此不支持随机访问
• LinkedList实现了Deque接口，Deque接口是双端队列接口，所以LinkedList作为它的实现类，可以为Deque接口引用赋值。
• LinkedList实现了Cloneable接口，表明LinkedList是可以clone的
• LinkedList实现了Serializable接口，表明LinkedList是支持序列化的

---

构造

方法	解释
LinkedList()	无参构造
LinkedList(Collection<? extends E> c)	使用其他集合容器中的元素构造（必须实现了Collection接口）

    public static void main(String[] args) {//无参构造LinkedList<Integer> linkedList = new LinkedList();ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);//其他容器构造LinkedList<Integer> linkedList1 = new LinkedList<>(arrayList);}

---

方法

LinkedList的方法有很多，常用方法如下：

方法	解释
boolean add(E e)	默认尾插 e
void add(int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection c)	尾插 c 中所有元素
E remove(int index)	删除 index 位置元素
boolean remove(Object o)	删除第一个 o
E get(int index)	获取 index 位置元素
E set(int index, E element)	将 index 位置元素设为 element
void clear()	清空
boolean contains(Object o)	判断 o 是否在线性表中
int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个 o 所在下标
List subList(int fromIndex, int toIndex)	截取 [fromIndex, toIndex) 的list
void addFirst(E element)	头插 element
void addLast(E element)	尾插 element
int size()	返回有效元素个数

部分演示代码：

    public static void main(String[] args) {LinkedList<Integer> linkedList = new LinkedList<>();linkedList.add(1);linkedList.addFirst(0);linkedList.set(1, 2);linkedList.addLast(3);linkedList.addLast(3);linkedList.addLast(4);linkedList.addLast(5);System.out.println("当前元素个数：" + linkedList.size());System.out.println(linkedList);System.out.println("2元素在表吗？：" + linkedList.contains(2));linkedList.remove(Integer.valueOf(3));System.out.println(linkedList);System.out.println("4在位置：" + linkedList.indexOf(4));linkedList.clear();System.out.println("清空后:" + linkedList);}

---

遍历

LinkedList的遍历方法有三种：for循环、for-each循环 和 迭代器

如下：

    public static void main(String[] args) {List<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);//for循环System.out.println("=====for循环=====");for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println();//for-each循环System.out.println("=====for-each循环=====");for(Integer x : list) {System.out.print(x + " ");}System.out.println();//迭代器System.out.println("=====Iterator=====");Iterator<Integer> it = list.iterator();while(it.hasNext()) {System.out.print(it.next() + " ");}System.out.println();System.out.println("=====ListIterator=====");ListIterator lit = list.listIterator();while(lit.hasNext()) {System.out.print(lit.next() + " ");}System.out.println();System.out.println("=====逆序输出=====");lit = list.listIterator(list.size());while(lit.hasPrevious()) {System.out.print(lit.previous() + " ");}System.out.println();}

---

LinkedList的模拟实现

实现一个双向链表，即结点有一个数据域、两个引用域（next 和 prev），同时，在链表类中加入两个成员变量head和tail分别指向链表的第一个和最后一个结点，实现的方法和使用到的自定义异常与上文实现单链表一致。

框架如下所示，clear、size、contains、display方法与单链表基本一致，其他方法仅给出大体思路，读者画图解决即可。

public class MyLinkedList implements IList {//结点类static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode tail;@Overridepublic void addFirst(int data) {}@Overridepublic void addLast(int data) {}@Overridepublic void addIndex(int index, int data) {}@Overridepublic boolean contains(int key) {if(head == null) {return false;}ListNode cur = this.head;while(cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}@Overridepublic void remove(int key) {}@Overridepublic void removeAllKey(int key) {}@Overridepublic int size() {int count = 0;ListNode cur = this.head;while(cur != null) {count++;cur = cur.next;}return count;}@Overridepublic void clear() {ListNode cur = head;while(cur != null) {ListNode curN = cur.next;cur.next = null;cur.prev = null;cur = curN;}tail = head = null;}@Overridepublic void display() {ListNode cur = this.head;while(cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}
}

---

public void addFirst(int data)

头插时，注意链表为空的情况；如果不为空，则需要改变3个指向：

• 新结点的next
• 原头指针的prev
• 头指针

注意2、3不能调换

    public void addFirst(int data) {ListNode newNode = new ListNode(data);if(head == null) {head = tail = newNode;return;}newNode.next = head;head.prev = newNode;head = newNode;}

---

public void addLast(int data)

头插时，同样注意链表为空的情况；如果不为空，则需要改变3个指向：

• 新结点的prev
• 原尾指针的next
• 尾指针

注意1、3不能调换

    public void addLast(int data) {ListNode newNode = new ListNode(data);if(head == null) {head = tail = newNode;return;}tail.next = newNode;newNode.prev = tail;tail = newNode;}

---

public void addIndex(int index,int data)

双向链表存在prev，所以不需要额外的引用存放前一个结点，代码步骤如下：

1. 判断下标合法性
2. 为头插
3. 为尾插
4. 为中间插，需要改变4个指向，画图分析即可

    public void addIndex(int index, int data) {if(index < 0 || index > size()) {throw new IllegalIndexException("Illegal Index !: 下标非法！");}if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}ListNode newNode = new ListNode(data);int count = 1;ListNode cur = this.head.next;while(cur != null) {if(count == index) {cur.prev.next = newNode;newNode.next = cur;newNode.prev = cur.prev;cur.prev = newNode;return;}count++;cur = cur.next;}}

---

public void remove(int key)

考虑的特殊情况较多，具体见代码注释

   public void remove(int key) {if(head == null) {throw new ListIsEmptyException("List Is Empty !: 链表为空!");}ListNode cur = this.head;while(cur != null) {//if为真，找到了指定结点if(cur.val == key) {//该结点为头结点if(cur == head) {head = head.next;//判断该结点是否是链表唯一一个结点，防止空指针异常if(cur.next == null) {head = tail = null;}else {head.prev = null;}}else {cur.prev.next = cur.next;//该结点为尾结点if (cur == tail) {tail = cur.prev;} else {cur.next.prev = cur.prev;}return;}}cur = cur.next;}}

---

public void removeAllKey(int key)

实现了remove方法，removeAllKey方法就十分简单，只需要删除return语句即可，使得找到一个待删除结点后继续寻找，而不是直接返回。

    public void removeAllKey(int key) {if(head == null) {throw new ListIsEmptyException("List Is Empty !: 链表为空!");}ListNode cur = this.head;while(cur != null) {if(cur.val == key) {if(cur == head) {head = head.next;if(cur.next == null) {head = tail = null;}else {head.prev = null;}}else {cur.prev.next = cur.next;if (cur == tail) {tail = cur.prev;} else {cur.next.prev = cur.prev;}}}cur = cur.next;}}

---

完整实现

public class MyLinkedList implements IList {//结点类static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode tail;@Overridepublic void addFirst(int data) {ListNode newNode = new ListNode(data);if(head == null) {head = tail = newNode;return;}newNode.next = head;head.prev = newNode;head = newNode;}@Overridepublic void addLast(int data) {ListNode newNode = new ListNode(data);if(head == null) {head = tail = newNode;return;}tail.next = newNode;newNode.prev = tail;tail = newNode;}@Overridepublic void addIndex(int index, int data) {if(index < 0 || index > size()) {throw new IllegalIndexException("Illegal Index !: 下标非法！");}if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}ListNode newNode = new ListNode(data);int count = 1;ListNode cur = this.head.next;while(cur != null) {if(count == index) {cur.prev.next = newNode;newNode.next = cur;newNode.prev = cur.prev;cur.prev = newNode;return;}count++;cur = cur.next;}}@Overridepublic boolean contains(int key) {if(head == null) {return false;}ListNode cur = this.head;while(cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}@Overridepublic void remove(int key) {if(head == null) {throw new ListIsEmptyException("List Is Empty !: 链表为空!");}ListNode cur = this.head;while(cur != null) {if(cur.val == key) {if(cur == head) {head = head.next;if(cur.next == null) {head = tail = null;}else {head.prev = null;}}else {cur.prev.next = cur.next;if (cur == tail) {tail = cur.prev;} else {cur.next.prev = cur.prev;}return;}}cur = cur.next;}}@Overridepublic void removeAllKey(int key) {if(head == null) {throw new ListIsEmptyException("List Is Empty !: 链表为空!");}ListNode cur = this.head;while(cur != null) {if(cur.val == key) {if(cur == head) {head = head.next;if(cur.next == null) {head = tail = null;}else {head.prev = null;}}else {cur.prev.next = cur.next;if (cur == tail) {tail = cur.prev;} else {cur.next.prev = cur.prev;}}}cur = cur.next;}}@Overridepublic int size() {int count = 0;ListNode cur = this.head;while(cur != null) {count++;cur = cur.next;}return count;}@Overridepublic void clear() {ListNode cur = head;while(cur != null) {ListNode curN = cur.next;cur.next = null;cur.prev = null;cur = curN;}tail = head = null;}@Overridepublic void display() {ListNode cur = this.head;while(cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}
}

---

ArrayList与LinkedList区别

不同点	ArrayList	LinkedList
存储空间	物理上和逻辑上一定连续	逻辑上连续，物理上不一定连续
随机访问	支持，O(1)	不支持，O(N)
插入	头插和中间插需要移动元素，O(N)	只需要修改引用的指向，O(1)
容量	空间不足时需要扩容	没有容量的概念，使用时直接实例化结点对象
应用场景	元素高效存储 + 频繁访问	插入和删除操作频繁

---

链表的相关练习

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {//补充代码}
}

对于这个题目我们给出两个思路：

【思路一】

采用头插法，定义一个引用变量，遍历原链表的每个结点，并将每个结点头插到新引用变量的链表中

	/***头插法*/public ListNode reverseList(ListNode head) {if(head == null) {return head;}ListNode newHead = null;//新的头引用ListNode cur = head;while(cur != null) {//临时存放下一个结点ListNode tmp = cur.next;//头插第一个，该结点一定是反转后链表的最后一个结点if(newHead == null) {newHead = cur;//作为最后一个结点，它的next要置空newHead.next = null;}else {//头插cur.next = newHead;newHead = cur;}cur = tmp;}return newHead;}

其实不定义新引用，在原head上修改也可以，避免了上面代码中每次都要if判断的弊端

	/***头插法*/public ListNode reverseList(ListNode head) {if(head == null) {return head;}ListNode cur = head.next;head.next = null;while(cur != null) {ListNode tmp = cur.next;cur.next = head;head = cur;cur = tmp;}return head;}

【思路二】

三"指针"法，也是直接在原链表上修改指向，一个遍历，一个记录遍历的前一个结点，再一个记录遍历的后一个结点

	/***三"指针"法*/public ListNode reverseList(ListNode head) {if(head == null) {return head;}ListNode prev = head;ListNode cur = head.next;//尾结点的next要为nullhead.next = null;while(cur != null) {ListNode curN = cur.next;cur.next = prev;prev = cur;cur = curN;}return prev;}

原题链接：206. 反转链表 - 力扣（LeetCode）

---

链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点；如果有两个中间结点，则返回第二个中间结点。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode middleNode(ListNode head) {//补充代码}
}

对于这个题目，最笨的办法就是遍历链表，求出链表的长度，然后根据长度寻找，但是有更好的办法：快慢指针法

即，定义两个引用，快引用一次走两步，慢引用一次走一步，当快引用走到null或最后一个结点时，慢引用指向的结点就是所求结点， 画图表示：

奇数结点：

偶数结点：

    public ListNode middleNode(ListNode head) {if(head == null) {return head;}ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}return slow;}

原题链接：876. 链表的中间结点 - 力扣（LeetCode）

---

链表的回文结构

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构

import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class PalindromeList {public boolean chkPalindrome(ListNode A) {//补充代码}
}

回文结构的链表正向遍历和反向遍历的结果一致，如1、1->1、1->2->2->1、1->2->3->2->1，空链表认为是回文结构的链表。

观察结点类，发现这是一个单链表，不能从后往前遍历，怎么办？这里建议读者停下来思考一会儿，思考没结果也没关系，我们直接看：

【思路】

先找到链表的中间结点，然后将中间结点后的结点反转，最后分别从头和尾开始向中间遍历依次判断值是否相等。所以，这一道题目是在上面两道题目的基础上设置的，不算难。

关键在第三步，确定遍历的结束条件，区分奇偶个结点情况：

奇数： 遍历判断结束的条件为A == slow

偶数： 遍历判断结束的条件为A.next == slow

如下代码：

    public boolean chkPalindrome(ListNode A) {if(A == null) {return true;}//寻找中间结点ListNode fast = A;ListNode slow = A;while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}//slow位置为中间结点，开始反转，这里使用三指针法ListNode cur = slow.next;while(cur != null) {ListNode curN = cur.next;cur.next = slow;slow = cur;cur = curN;}//slow最终指向最后一个结点，与头结点A开始向中间遍历判断while(slow != A && A.next != slow) {if(slow.val != A.val) {return false;}slow = slow.next;A = A.next;}}

原题链接：链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

---

判断链表是否有环

给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {//补充代码}
}

要解决这个问题，我们得清楚什么是环形链表，结合题目和如图：

如图，-4结点又回到2结点，那么会不会出现0回到2的情况呢？

不会的，如果0回到2，0又得到达-4，0结点就得有两个next，显然不成立。

【思路】

快慢指针法，如果不存在环，那么快指针一定优先到达尾结点或null（奇偶数结点）；如果有环，那么快指针会先入环，一旦慢指针入环，快指针会追赶慢指针，每走一次，距离缩短1，最终会追上慢指针（当然快指针一定会套圈，比慢指针至少多走一圈）

如果快指针一次走3、4、5……n步，慢指针走一步可以吗？

以快指针走3步为例：

当快指针在b结点时，慢指针在a结点刚入环，继续走，快慢指针永远不会相遇，会刚好一直套圈，所以我们直接采用快指针走2步，慢指针走1步即可

---

有了上述思路，代码就很简单了：

    public boolean hasCycle(ListNode head) {if(head == null) {return false;}ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if(fast == slow) {return true;}}return false;}

原题链接：141. 环形链表 - 力扣（LeetCode）

---

寻找入环的第一个结点

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {//补充代码}
}

如图，返回2结点。

我们知道，当链表带环，快指针一次走2，慢指针一次走1，它们一定会在环内相遇，有如下结论：

快慢指针在环内的相遇点到入环第一个结点的距离 等于 链表起始结点到入环第一个结点的距离

【证明结论】

先画草图：

假设：

• 链表起点到入环结点的距离为L
• 入环结点到相遇点的距离为X
• 环的长度为C
• 所以 相遇点到入环结点的距离为C-X

已知：

• 快指针走过的路程为慢指针的2倍

• 快慢指针相遇时，快指针一定至少走完了一圈，快指针最好情况下是在第二圈与慢指针相遇

• 慢指针入环后，快指针一定会在慢指针走一圈内与慢指针相遇，因为慢指针入环后，两个指针的距离最多为环的长度，而两个指针每次移动距离都缩小1步

我们先讨论快指针走第二圈就与慢指针相遇的情况，根据假设和已知条件可得：

快指针路程：L + C + X

慢指针路程：L + X

所以有：L + C + X = 2 × ( L + X )

化简得：C - X = L

与结论一致！

但是上面只是一种情况，假设：相遇时，快指针已经走了N圈：

快指针路程：L + N×C + X

慢指针路程：L + X

所以有：L + N×C + X = 2 × ( L + X )

化简得：L = N×C - X

​ L = （ N - 1 ）× C + C - X（环越小，N越大）

得证！（相遇时，快指针已经将（ N - 1 ）× C 走完）

即，先让快慢指针相遇，然后让其中一个指针从头开始，另一个指针从相遇点开始，两个均一次走1步，再次相遇的点就是入环的第一个结点。

所以，可以开始书写代码：

    public ListNode detectCycle(ListNode head) {if(head == null) {return head;}//判断是否有环ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if(slow == fast) {break;}}if(fast == null || fast.next == null) {return null;}//寻找入环结点slow = head;while(fast != slow) {slow = slow.next;fast = fast.next;}return slow;}

原题链接：142. 环形链表 II - 力扣（LeetCode）

---

还有一些题目不再讲解，自行练习：

21. 合并两个有序链表 - 力扣（LeetCode）

链表分割_牛客题霸_牛客网 (nowcoder.com)

160. 相交链表 - 力扣（LeetCode）

---

完