链表理论基础
基本说明
由于数组的长度都是固定的，如果数组已被数据填满，再要加入新的元素是非常困难的。而且，对于数组的删除和添加操作，通常需要将数组中的其他元素向前或者向后平移，这些操作也十分繁琐。
链表是一种通过指针串联在一起的存储非连续线性结构，每个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（也就是空指针）。链表的入口节点称为链表的头结点也就是head。
链表在Java中有两种：单向链表、双向链表。至于循环列表，可用这两种基础的链表结构实现。Java自带LinkedList类，其底层为双向列表，其构造方法分为有参/无参，需要导入泛型。相关的API方法在题目涉及到时进行详解。
操作方式
删除节点：将前一节点指针指向后一节点即可。Java不需要内存释放。
添加节点：前一节点指针指向新节点，新节点指针指向后一节点。
关键原理：如果要对某个节点进行增删，那么操作的一定是此节点位置的前一个节点。
简单题
[203]移除链表元素、[206]反转链表（双指针法）
采用虚拟头节点法，方便进行增删操作。在结束时，返回处理后的头节点（即虚拟头节点的下一跳）。在刷题前，设置一个util包，专门存放自定义的数据结构，重写后的ListNode如下：
public class ListNode {
public int val;
public ListNode next;
public ListNode() {
}
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
中等题
[707]设计链表
题设：你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类：
-
MyLinkedList()初始化MyLinkedList对象。 -
int get(int index)获取链表中下标为index的节点的值。如果下标无效，则返回-1。 -
void addAtHead(int val)将一个值为val的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。 -
void addAtTail(int val)将一个值为val的节点追加到链表中作为链表的最后一个元素。 -
void addAtIndex(int index, int val)将一个值为val的节点插入到链表中下标为index的节点之前。如果index等于链表的长度，那么该节点会被追加到链表的末尾。如果index比长度更大，该节点将 不会插入 到链表中。 -
void deleteAtIndex(int index)如果下标有效，则删除链表中下标为index的节点。
思路：手撕链表看似是中等题，实际上通过率比困难题更低，因为其中需要注意非常多的细节。本题要求的五个接口，已经覆盖了链表的常见操作，是练习链表操作非常好的一道题目。还是采用虚拟头节点的方式，基于单链表根据要求一步步实现。
class MyLinkedList {
//元素个数
int size;
//虚拟头节点
ListNode head;
//链表初始化
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
//获取链表中下标为 index 的节点值
public int get(int index) {
if (index >= size) return -1;
ListNode cur = head;
for (int i = 0; i <= index; i++) cur = cur.next; //由于包含虚拟头节点，所以查找第 index+1 个
return cur.val;
}
//将一个值为 val 的节点插入到链表中第一个元素之前
public void addAtHead(int val) {
addAtIndex(0, val);
}
//将一个值为 val 的节点追加到链表中作为链表的最后一个元素
public void addAtTail(int val) {
addAtIndex(size, val);
}
//将一个值为 val 的节点插入到链表中下标为 index 的节点之前
//如果 index 等于链表的长度，那么该节点会被追加到链表的末尾
//如果 index 比长度更大，该节点将不会插入到链表中
public void addAtIndex(int index, int val) {
if (index > size) return;
size++;
ListNode pre = head;
for (int i = 0; i < index; i++) pre = pre.next;
ListNode toAdd = new ListNode(val);
toAdd.next = pre.next;
pre.next = toAdd;
}
//如果下标有效，则删除链表中下标为 index 的节点
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) return;
size--;
if (index == 0) {
head = head.next;
return; //处理完特殊情况后直接返回
}
ListNode pre = head;
for (int i = 0; i < index; i++) pre = pre.next;
pre.next = pre.next.next;
}
}
[206]反转链表（递归法）
题设：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
思路：双指针的解法是简单题的难度，从前往后将每条路翻转。递归法其实和双指针是同一个逻辑，只是理解起来稍难一点。
class Solution {
public ListNode reverseList(ListNode head) {
return reverse(null, head);
}
public ListNode reverse(ListNode pre, ListNode cur) {
if (cur == null) return pre;
ListNode temp = cur.next;
cur.next = pre;
return reverse(cur, temp);
}
}
其中，return reverse(cur, temp);这一步，实际上完成了pre=cur;和cur=temp;两步。
时间复杂度：O(n)，每一次递归都处理链表中的一个节点。
空间复杂度：O(n)，递归调用了n层栈，其实要比双指针法占用更多空间。
[24]两两交换链表中的节点
题设：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
思路：虚拟头节点+画图解决。交换两个相邻节点时的操作顺序需要格外注意。
根据以上操作顺序（实际写代码时需要反着写），可得：
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1, head);
ListNode cur = dummy;
ListNode first;
ListNode second;
while (cur.next != null && cur.next.next != null) {
first = cur.next;
second = first.next;
first.next = second.next;
second.next = first;
cur.next = second;
cur = first;
}
return dummy.next;
}
}
时间复杂度：O(n)，需要遍历链表中的所有节点。
空间复杂度：O(1)，在遍历过程中，并未开辟新的内存空间。
[19]删除链表的倒数第N个节点
题设：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
思路：双指针法的经典应用。具体操作为，两个指针都先指向头节点，快指针先走n步，再同时移动快慢指针，当快指针指向最后一个节点时，慢指针就会指向要删除的目标节点的头节点。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1, head);
ListNode slow = dummy;
ListNode fast = dummy;
for (int i = 0; i < n; i++) fast = fast.next;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
时间复杂度：O(n)，需要遍历链表中的所有节点，用双指针法只需要遍历一遍。
空间复杂度：O(1)，在遍历过程中，并未开辟新的内存空间。
[160]链表相交
题设：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
-
intersectVal- 相交的起始节点的值。如果不存在相交节点，这一值为0 -
listA- 第一个链表 -
listB- 第二个链表 -
skipA- 在listA中（从头节点开始）跳到交叉节点的节点数 -
skipB- 在listB中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
思路：此题的含义是指针指向同一个节点，而不是节点值相同。方法一：长度长的链表截掉2个链表的差值后，再和长度短的链表一一进行比较，这种方法被称为先行移动长列表。方法二：合并链表实现同步移动，也是本次使用的方法。两个链表同时移动，当短链表达到末尾时，长链表正好达到比短链表多余的部分。此时，让短链表指针从长链表开始遍历，当长链表遍历结束时从短链表开始遍历，就可以达到和方法一一样的效果。同时可以发现，无论短链还是长链，遍历后都从另一个链表开始，所以其实根本不需要判断孰长孰短。
class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA;
ListNode p2 = headB;
while (p1 != p2) {
if (p1 == null) p1 = headB;
else p1 = p1.next;
if (p2 == null) p2 = headA;
else p2 = p2.next;
}
return p1;
}
}
时间复杂度：O(n+m)，需要同时遍历长链表和短链表。
空间复杂度：O(1)，在遍历时不需要创建新的空间。
[142]环形链表II
题设：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
思路：本题分为2个步骤：1.确定是否有环；2.确定环开始的位置。学过奥数的应该知道，设置快慢两个指针，慢指针每次走一格，快指针每次走两格，若路径含环，则二者终相遇。确定入环位置时，有如下图：
首先，慢指针在入环的第一圈二者就会相遇。（慢指针走一圈的时间内，快指针一定走了两圈）此时慢指针走过的路程为x+y，快指针走过的路程为x+z+2y，乂，快指针移动速度正好为慢指针的两倍，所以有：2*(x+y)=x+z+2y，消去重复项后可得x=z！从快慢指针相遇节点和头节点同时开始，其相遇的地方便是环的入口。
class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode p1 = slow;
ListNode p2 = head;
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
}
return null;
}
}
时间复杂度：O(n)，因为快慢指针相遇前，指针走的次数小于链表长度，快慢指针相遇后，两个p指针走的次数也小于链表长度，总体走的次数小于链表长度的两倍。
空间复杂度：O(1)，满足题目的要求，并没有修改或创建链表。
总结
