本文非原创，为摘录网络内容

1 简介

1.1 单链表

单链表的典型定义：

  1. public class ListNode{
  2.     int val;
  3.     ListNode next;
  4.     ListNode(int x){val = x;}
  5. }

1.2 双链表

双链表的定义：

  1. public class ListNode{
  2.     int val;
  3.     ListNode next,prev;
  4.     ListNode(int x){val = x;}
  5. }

双链表在插入和删除的时候要考虑前继节点

1.3 设计链表

707. 设计链表
单链表的写法:

  1. class ListNode {
  2.     int val;
  3.     ListNode next;
  4.     ListNode(){};
  5.     ListNode(int x){
  6.         this.val = x;
  7.     } 
  8. }
  9. class MyLinkedList {
  10.     int size ; //存储数量
  11.     ListNode head; //虚拟头节点
  12.     /** Initialize your data structure here. */
  13.     public MyLinkedList() {
  14.         size = 0;
  15.         head = new ListNode(0);
  16.     }
  18.     /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
  19.     public int get(int index) {
  20.         if(index>=size || index < 0){
  21.             return -1;
  22.         }
  23.         ListNode node = head;
  24.         for(int i = 0 ; i <= index; i++){
  25.             node = node.next;
  26.         }
  27.         return node.val;
  28.     }
  30.     /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
  31.     public void addAtHead(int val) {
  32.         addAtIndex(0,val);
  33.     }
  35.     /** Append a node of value val to the last element of the linked list. */
  36.     public void addAtTail(int val) {
  37.         addAtIndex(size,val);
  38.     }
  40.     /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
  41.     public void addAtIndex(int index, int val) {
  42.         if(index > size) return;
  43.         ListNode addNode = new ListNode(val); 
  44.         if(index < 0){
  45.             index = 0; 
  46.         }
  47.         ListNode preNode = head;
  48.         for(int i = 0 ; i < index; i++){
  49.             preNode = preNode.next;
  50.         }
  51.         addNode.next = preNode.next;
  52.         preNode.next = addNode;
  53.         size++;
  54.     }
  56.     /** Delete the index-th node in the linked list, if the index is valid. */
  57.     public void deleteAtIndex(int index) {
  58.         if(index >= size || index < 0) return;
  59.         ListNode preNode = head;
  60.         for(int i = 0 ; i < index ; i++){
  61.             preNode = preNode.next;
  62.         }
  63.         preNode.next = preNode.next.next;
  64.         size--;
  65.     }
  66. }
  68. /**
  69.  * Your MyLinkedList object will be instantiated and called as such:
  70.  * MyLinkedList obj = new MyLinkedList();
  71.  * int param_1 = obj.get(index);
  72.  * obj.addAtHead(val);
  73.  * obj.addAtTail(val);
  74.  * obj.addAtIndex(index,val);
  75.  * obj.deleteAtIndex(index);
  76.  */

双链表的写法：

  1. class MyLinkedList {
  2.     class ListNode{
  3.         int val;
  4.         ListNode next,prev;
  5.         ListNode(int x){
  6.             val = x;
  7.         }
  8.     }
  9.     int size;
  10.     ListNode head, tail;
  11.     /** Initialize your data structure here. */
  12.     public MyLinkedList() {
  13.         size = 0;
  14.         head = new ListNode(0);
  15.         tail = new ListNode(0);
  16.         head.next = tail;
  17.         tail.prev = head;
  18.     }
  20.     /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
  21.     public int get(int index) {
  22.         if(index < 0 || index >= size) return -1;
  23.         ListNode cur = head;
  24.         //头节点遍历还是尾结点遍历
  25.         if(index < (size-1)/2){
  26.            for(int i = 0 ; i <=index ; i++){
  27.             cur = cur.next;
  28.             } 
  29.         }else{
  30.             cur = tail;
  31.             for(int i = 0 ; i <= size - index - 1;i++){
  32.                 cur = cur.prev;
  33.             }
  34.         }
  35.         return cur.val;
  36.     }
  38.     /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
  39.     public void addAtHead(int val) {
  40.         ListNode addNode = new ListNode(val);
  41.         ListNode cur = head;
  42.         cur.next.prev = addNode;
  43.         addNode.next = cur.next;
  44.         cur.next = addNode;
  45.         addNode.prev = cur;
  46.         size++;
  47.     }
  49.     /** Append a node of value val to the last element of the linked list. */
  50.     public void addAtTail(int val) {
  51.         ListNode addNode = new ListNode(val);
  52.         ListNode cur = tail;
  53.         cur.prev.next = addNode;
  54.         addNode.prev = cur.prev;
  55.         addNode.next = cur;
  56.         cur.prev = addNode;
  57.         size++;
  58.     }
  60.     /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
  61.     public void addAtIndex(int index, int val) {
  62.         if(index > size) return;
  63.         if(index < 0) index = 0;
  64.         ListNode curNode = head;
  65.         for(int i = 0 ; i < index; i++){
  66.             curNode =  curNode.next;
  67.         }
  68.         ListNode addNode = new ListNode(val);
  69.         addNode.next = curNode.next;
  70.         curNode.next.prev = addNode;
  71.         curNode.next = addNode;
  72.         addNode.prev = curNode;
  73.         size++;
  74.     }
  75.     //找到前一个index前的第一个节点
  76.     /** Delete the index-th node in the linked list, if the index is valid. */
  77.     public void deleteAtIndex(int index) {
  78.         if(index >= size || index < 0 ) return;
  79.         ListNode pre = head;
  80.         for(int i = 0 ; i < index; i++){
  81.             pre = pre.next;
  82.         }
  83.         ListNode t = pre.next.next;
  84.         pre.next = t;
  85.         t.prev = pre;
  86.         size--;
  87.     }
  88. }

2. 链表中的双指针技巧

在链表中使用两个速度不同的指针会发生的情况：

  1. 如果不存在环，快指针会停在链表的末尾；
  2. 如果有环，快指针最终会与慢指针相遇

一个安全的选择是每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。

需要注意快指针和慢指针的起点是否一致（有些题目需要保持一致）

  1. // Initialize slow & fast pointers
  2. ListNode slow = head;
  3. ListNode fast = head;
  4. /**
  5.  * Change this condition to fit specific problem.
  6.  * Attention: remember to avoid null-pointer error
  7.  **/
  8. while (slow != null && fast != null && fast.next != null) {
  9.     slow = slow.next;           // move slow pointer one step each time
  10.     fast = fast.next.next;      // move fast pointer two steps each time
  11.     if (slow == fast) {         // change this condition to fit specific problem
  12.         return true;
  13.     }
  14. }
  15. return false;   // change return value to fit specific problem

除此之外，需要注意：

  1. 在调用 next 字段之前，始终检查节点是否为空。

获取空节点的下一个节点将导致空指针错误。例如，在我们运行 fast = fast.next.next 之前，需要检查 fast 和 fast.next 不为空。

  1. 仔细定义循环的结束条件。

链表环问题【以下问题中，快慢指针同节点】
参考《漫画算法：小灰的算法之旅》
1、如果链表有环，怎么求出环的长度？
当两个指针首次相遇，证明链表有环的时候，让两个指针从相遇点继续循环前进，并统计前进的循环 次数，直到两个指针第2次相遇。此时，统计出来的前进次数就是环长。
2、如果链表有环，如何求出入环节点？
image.png
也就是说，从链表头结点到入环点的距离，等于从首次相遇点绕环n-1圈再回到入环点的距离。
这样一来，只要把其中一个指针放回到头节点位置，另一个指针保持在首次相遇点，两个指针都是每 次向前走1步。那么，它们最终相遇的节点，就是入环节点。

相关题目：
142. 环形链表 II
160. 相交链表
19. 删除链表的倒数第 N 个结点

3 链表经典问题

在解决链表问题时，我们常常可以使用守卫节点来简化操作，如

  1. ListNode dummyNode = new ListNode();
  2. dummyNode.next = head;

234. 回文链表 使用递归去解决问题
430. 扁平化多级双向链表
138. 复制带随机指针的链表