LeetCode 热题 100 | 链表

链表基础

• 链表的种类主要为：单链表，双链表，循环链表
• 链表的存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。
• 链表是如何进行增删改查的。增删是O(1)，改查是O(n)。改查需要从head开始遍历查询特定位置，不像数组直接下标锁定位置。
• 160. 相交链表

1. 哈希表存储链表方便快速查找
2. 双指针调换随指向的链表，方便调换之后从同一长度开始查找。

• 206. 反转链表

1. 迭代法
2. 递归法

160. 相交链表

题目讲解：LeetCode
重点：

1. 哈希表存储其中一个链表，另一个链表用哈希表来快速查找
2. 双指针创建两个指针 pA 和 pB，然后开始遍历。如果A比B长, 则pB会先跳到headA，随后pA也会调到headB，调换之后将能够从同一长度开始遍历。

思路：

• 哈希表

1. 遍历链表 headA，将链表 headA 中的节点加入哈希表中
2. 遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希表中

• 双指针（证明思路看力扣题解 - 方法二）

1. 创建两个指针 pA 和 pB，初始化指向 headA 和 headB
2. 如果指针 pA 不为空，则将指针 pA 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点。
3. 如果指针 pA 为空，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点。
4. 当指针 pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。

复杂度：

• m 是链表A的长度。n 是链表B的长度。
• 哈希表
  时间复杂度：O(m + n)。需要遍历两个链表各一次。
  空间复杂度：O(m)
• 双指针
  时间复杂度：O(m + n)
  空间复杂度：O(1)

// 哈希表
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 哈希集合存储A, 方便B快速查找是否有相同Set<ListNode> headASet = new HashSet<>();ListNode temp = headA;while (temp != null) {headASet.add(temp);temp = temp.next;}temp = headB;while (temp != null) {if (headASet.contains(temp)) return temp;temp = temp.next;}return null;
}

// 双指针
// 创建两个指针 pA 和 pB，然后开始遍历。如果A比B长, 则pB会先跳到headA，随后pA也会调到headB，调换之后将能够从同一长度开始遍历。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) return null;ListNode pA = headA, pB = headB;// 如果A比B长, 则pB会先跳到headA, 随后pA也会调到headB, 辅助从同一长度开始遍历// 可以自己模拟一遍while (pA != pB) {if (pA == null) {pA = headB;} else {pA = pA.next;}if (pB == null) {pB = headA;} else {pB = pB.next;}}return pA;
}

206. 反转链表

题目讲解：LeetCode
重点：

1. 迭代法，pre，cur和temp。
2. 递归法，编写一个递归函数。

思路：

• 迭代法

1. 三个指针。cur当前，pre前一个，temp下一个。先让temp指向下一个，然后改cur，最后移动pre和cur。

• 递归法

1. 递归函数的参数有pre和cur，返回值为ListNode
2. 终止条件是cur为null的时候。
3. 单层递归的处理逻辑则跟迭代法一致。

复杂度：

• n 是链表的长度
• 迭代法
  时间复杂度：O(n)
  空间复杂度：O(1)
• 递归法
  时间复杂度：O(n)
  空间复杂度：O(n)。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。

// 迭代法
public ListNode reverseList(ListNode head) {ListNode cur = head;ListNode pre = null;ListNode temp;while (cur != null) {temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;
}

// 递归法
private ListNode reverse(ListNode pre, ListNode cur) {if (cur == null) return pre;ListNode temp = cur.next;cur.next = pre;pre = cur;cur = temp;return reverse(pre, cur);
}
public ListNode reverseList(ListNode head) {return reverse(null, head);
}

题目讲解：LeetCode
重点：
1.

思路：
1.

复杂度：

时间复杂度：O(mn)
空间复杂度：O(m+n)

题目讲解：LeetCode
重点：
1.

思路：
1.

复杂度：

时间复杂度：O(mn)
空间复杂度：O(m+n)

题目讲解：LeetCode
重点：
1.

思路：
1.

复杂度：

时间复杂度：O(mn)
空间复杂度：O(m+n)

题目讲解：LeetCode
重点：
1.

思路：
1.

复杂度：

时间复杂度：O(mn)
空间复杂度：O(m+n)

题目讲解：LeetCode
重点：
1.

思路：
1.

复杂度：

时间复杂度：O(mn)
空间复杂度：O(m+n)