作为线性表的两种存储方式 —— 链表和数组，这对相爱相杀的好基友有着各自的优缺点。接下来，我们梳理一下这两种方式。
数组数组是内存中一块给定固定大小且连续的区域。
数组特点：增删慢（n），改查快（1）。
增加元素：
情况一：在头位置增加，这是最坏的情况，因为后续所有位置都要后移。 情况二：在中间位置增加，该位置后面的所有元素要后移。如果此时固定大小的数组容量不够，需要重新定义数组。 情况三：在尾部增加，这是最好的情况，不需要移动任何元素，时间复杂度是1。 时间复杂度一般看最坏或者平均，所以对于数组增加操作我们默认是O（n）。
删除元素：
同增加元素类似，分三种情况。 情况一：头部删除元素，需要将后续所有元素左移。 情况二：中间位置删除元素只需要将该位置后的所有元素左移就可以了。 情况三：尾部元素删除元素，不需要移动元素。 注意：和增加元素不同的是增加可能导致扩容或者说需要重新定义数组的问题，而删除元素没有这个问题。
改查元素
因为数组在内存中是连续存储的区域，所以知道了数组第一个元素的位置就可以数组的所有位置，而nums就是nums[0]的地址值，因此数组中查找某个元素的时间复杂度是O（1），查找后修改即可，也是O（1）.链表
链表和数组正好相反，由若干个结点组成，每个结点包含数据域和指针域。结点结构如下图所示：
链表特点：增删快，改查慢，正好与数组相反。
链表分为具有头节点和不带头结点的链表，插入方式又分为头插法和尾插法，具体看下图。
头插法
链表具有头节点，头指针和首元节点，具体看下图
尾插法
带头结点的链表
无头结点的链表
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//n n
HashSet set = new HashSet<>();
ListNode p1 = headA, p2 = headB;
while (p1 != null) {
set.add(p1);
p1 = p1.next;
}
while (p2 != null) {
if (!set.add(p2)) return p2;
p2 = p2.next;
}
return null;
}
}
23. 合并K个升序链表
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
//时空复杂度：nlogn n
PriorityQueue pq = new PriorityQueue(lists.length, (a, b) -> (a.val - b.val));//优先级队列，最⼩堆
ListNode dummy = new ListNode(-1), p = dummy;//虚拟头结点
for (ListNode list : lists) {//将 k 个链表的头结点加⼊最⼩堆
if (list != null) {
pq.add(list);
}
}
while (!pq.isEmpty()) {
ListNode poll = pq.poll();//获取最⼩节点，接到结果链表中
p.next = poll;
p = p.next;//p 指针不断前进
if (poll.next != null) {
pq.add(poll.next);
}
}
return dummy.next;
}
}
21. 合并两个有序链表（简单）
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 虚拟头结点
ListNode dummy = new ListNode(-1), p = dummy, p1 = list1, p2 = list2;
while (p1 != null && p2 != null) {
//⽐较 p1 和 p2 两个指针 // 将值较⼩的的节点接到 p 指针
if (p1.val > p2.val) {
p.next = p2;
p2 = p2.next;
} else {
p.next = p1;
p1 = p1.next;
}
p = p.next;//p 指针不断前进
}
if (p1 != null) {
p.next = p1;
}
if (p2 != null) {
p.next = p2;
}
return dummy.next;
}
}
2. 两数相加（中等）
因为链表和数字的顺序相反，所以直接相加，sum=l1.val+l2.val+carry.
每次res.val=sum%10, carry=sum/10。
如果链表长度不一致，短的用0补充。
最后如果都遍历完成了还有进位，需要额外补充一个新节点。比如50+50=100.
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null, tail = null;
int v1 = 0, v2 = 0, sum = 0, cary = 0;
while (l1 != null || l2 != null) {
v1 = l1 == null ? 0 : l1.val;//l1位数少，高位用0补充
v2 = l2 == null ? 0 : l2.val;//l2位数少，高位用0补充
sum = v1 + v2 + cary;
cary = sum / 10; //进位
//生成结果链表
if (head == null) {
head = tail = new ListNode(sum % 10);
} else {
tail.next = new ListNode(sum % 10);
tail = tail.next;
}
//分别右移l1和l2
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
//如果两个链表都遍历完还有进位，多加一个节点
if (cary != 0) {
tail.next = new ListNode(cary);
}
return head;
}
}
19. 删除链表的倒数第 N 个结点（中等）
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode p1 = dummy, p2 = dummy;
for (int i = 0; i <= n; i++) {
p2 = p2.next;
}
while (p2 != null) {
p2 = p2.next;
p1 = p1.next;
}
p1.next = p1.next.next;
return dummy.next;
}
876. 链表的中间结点（简单）
class Solution {
public ListNode middleNode(ListNode head) {
ListNode dummy = new ListNode(-1), p1 = dummy, p2 = dummy;
dummy.next = head;
while (p2 != null) {
p1 = p1.next;
if (p2.next != null) {
p2 = p2.next.next;
} else {
p2 = p2.next;
}
}
return p1;
}
}
141. 环形链表（简单）
判断单链表是否有环
//省略了base case的判断
for (ListNode i = head; i != null; i = i.next) {
//n2 1
for (ListNode j = head; j.next != i; j = j.next) {
if (i == j) return true;
}
}
哈希表缓存
public boolean hasCycle(ListNode head) {
//n n,相较于方法一是空间换时间
HashSet set = new HashSet<>();
while (head != null) {
if (!set.add(head)) {//add(x)如果set中不存在x返回true，否则，返回false
return true;
}
head = head.next;
}
return false;
}
快慢指针
当一个链表有环时，快慢指针都会陷入环中进行无限次移动，然后变成了追及问题。想象一下在操场跑步的场景，只要一直跑下去，快的总会追上慢的。当两个指针都进入环后，每轮移动使得慢指针到快指针的距离增加一，同时快指针到慢指针的距离也减少一，只要一直移动下去，快指针总会追上慢指针。
public boolean hasCycle(ListNode head) {
//n 1
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
双向链表判断是否有环
情况一：有next环，同单链表处理方式一致，只不过不知道尾节点的位置，不能识别pre环。
情况二：没有next环，找到尾节点，从尾节点逆着遍历pre，找到pre环。
求单链表环的位置
如果存在环，如何判断环的长度呢？方法是，快慢指针相遇后继续移动，直到第二次相遇。两次相遇间的移动次数即为环的长度。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break;
}
if (fast == null || fast.next == null) {
return null;
}
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
求双向链表环的位置
同单链表类似
