3. 链表

链表是一种通过指针串联在一起的线性结构，每一个结点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个结点的指针域指向null（空指针的意思）。　

1. 链表基础

　　单链表：指针域只指向结点的下一个结点。

　　双链表：每一结点有两个指针域，一个指向下一个结点，一个指向上一个结点（双向查询）。

　　循环链表：首尾相连，可以用来解决约瑟夫环问题。

2.  移除链表元素（主要是处理头结点的问题）

　　头部使用虚结点

　　　　ListNode dummy = new ListNode(-1, head); // 需要有双参数的构造函数

　　头部对头结点进行处理

　　　　while (head != null && head.val == val) { head = head.next; }

　　　　// 已经为null，提前退出

　　　　if (head == null) { return head;}

3. 设计链表（力扣707）（虚拟头结点法 或 虚拟头结点+尾结点法）

　　虚拟头结点法：使用虚拟结点（以下关于 n 的计算都是从虚拟结点开始的，index 在 0 之前）

　　　　MyLinkedList类：（包含两个属性：当前链表元素的个数 size + 虚拟头结点 dummyHead）

• 　无参构造器中初始化应包含两部分：当前链表的长度 + 初始化虚拟头结点；

• 　get(int index) 方法获取指定index结点的值：

  public int get(int index) {
          // 超出链表索引的index返回-1;
          if (index < 0 || index >= size) {
              return -1;
          }
          ListNode curNode = dummyHead.next;
          // 要找到第n个元素，进行n-1次循环，targetNode就可以指向n结点，即为index所在的结点；
          for (int i = 0; i < index; i++) {
              curNode = curNode.next;
          }
          return curNode.val;
      }

• addAtIndex(int index, int val)

      public void addAtIndex(int index, int val) {
          // 力扣707会对链表头部和尾部操作，范围包括 index==size 和 index==0
          if (index > size || index < 0) {
              return;
          }
          size++;
          // 和删除结点的格式统一，所以也从虚拟结点开始
          ListNode addNode = dummyHead;
          // 虚拟结点开始，要在第n个结点插入，需要在第n-1个结点进行操作，进行n-1次循环，
          // index==0的结点开始，要在第n个结点插入，需要在第n-1个结点进行操作，进行n-2次循环，
          for (int i = 0; i < index; i++)
          {
              addNode = addNode.next;
          }
          ListNode newNode = new ListNode(val);
          // 顺序反过来会丢失结点；
          newNode.next = addNode.next;
          addNode.next = newNode;
      }

• addAtHead(int val)

      // 表示在头部插入一个值，也可以直接调用上面 addAtIndex()方法
      public void addAtHead(int val) {
          ListNode newNode = new ListNode(val);
          // 插入结点的时候 必须先把dummyHead的下一个结点，赋值给newNode.next，顺序反过来会丢失结点；
          newNode.next = dummyHead.next;
          dummyHead.next = newNode;
          size++;
      }

• addAtTail(int val)

      public void addAtTail(int val) {
          ListNode newNode = new ListNode(val);
          ListNode addNode = dummyHead;
          // 考虑下一个结点为null的情况就是尾部结点了，也可以循环n-1次到达尾部节点
          while (addNode.next != null) {
              addNode = addNode.next;
          }
          addNode.next = newNode;
          size++;
      }

• deleteAtIndex(int index)

      public void deleteAtIndex(int index) {
          if (index >= size || index < 0) {
              return;
          }
          size--;
          ListNode deleteNode = dummyHead;
          // 尾部结点，因为是从虚拟结点开始的，指针只会到n-1处；
          for (int i = 0; i < index; i++)
          {
              deleteNode = deleteNode.next;
          }
          deleteNode.next = deleteNode.next.next;
      }

4. 翻转链表

　　三种方法：

　　　　a. 开辟新的空间，实现链表元素反转，比较简单但是耗费内存；

　　　　b. 双指针法

　　　　c. 迭代法

　　　　双指针和迭代本质相同，都是从头开始，中间变量暂存当前元素后的链表，把当前结点翻转；

        while (cur != null) {
            temp = cur.next; // 暂存当前结点后的部分
            cur.next = pre; // 处理当前结点，翻转之后第一个结点后接的，其他结点接翻转之后的另一部分
            pre = cur; // 翻转
            cur = temp; // 当前结点后移
        }

5. 两两交换链表结点（力扣24）

6. 删除链表第n个结点（力扣19）

　　双指针，快指针先运动 n + 1 个结点，然后快慢指针一起运动；

7. 链表相交（力扣面试02.07）未解决。

8. 环形链表（力扣142）未解决。