一、链表相关算法
双指针
- 计数器的使用需严谨
- head结点不要随意修改，建议使用cur操作
- 要保证原链表不被破坏
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 1. 定义一个虚拟头结点，作为合并链表的头结点
ListNode ret = new ListNode(-1)；
// 2. 定义一个tmp结点，用于连接两个链表
ListNode tmp = ret;
// 3. 比较list1和list2的值
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
tmp.next = list1;
list1 = list1.next;
} else {
tmp.next = list2;
list2 = list2.next;
}
tmp = tmp.next;
}
// 如果比较完成后，某个链表还有剩余，说明来该链表剩余所有元素都比合并列表元素大，直接连接合并列表
if (list1 != null) {
tmp.next = list1;
}
if (list2 != null) {
tmp.next = list2;
}
return ret.next;
}
public ListNode partition(ListNode head, int x) {
// 1. 定义两个虚拟头结点，分别作为两个分隔链表的头结点
ListNode small = new ListNode(-1), big = new ListNode(-1);
// 2. 定义两个tmp结点，用于分别连接两个分隔链表
ListNode tmpSmall = small, tmpBig = big;
// 3.1 比较head.val与x的值
while (head != null) {
if (head.val < x) {
tmpSmall.next = head;
tmpSmall = tmpSmall.next;
} else {
tmpBig.next = head;
tmpBig = tmpBig.next;
}
// 3.2 如果在这写：head = head.next; 遇到原链表是环形链表就会报错
// 因为在连接分隔链表时不只连接了一个结点，是连接了后续整个链表
// 因此应主动切断结点的后续结点，后续也应保持这个习惯！
ListNode sep = head.next;
head.next = null;
head = sep;
}
// 4. 连接两个分隔链表
tmpSmall.next = big.next;
return small.next;
}
public ListNode mergeKLists(ListNode[] lists) {
// 特殊情况：如果传入的数组长度为0，返回空
if (lists.length == 0) {
return null;
}
// 1. 合并k个有序链表，首先应找到这k个链表的最小值。可以借助优先级队列得到最小值
PriorityQueue<ListNode> pq = new PriorityQueue<>(
lists.length, (a, b)->(a.val - b.val));
// 2.1 定义一个虚拟头结点，作为合并链表的头结点
ListNode ret = new ListNode(-1);
// 2.2 定义一个tmp结点，用于合并链表的连接
ListNode tmp = ret;
// 3. 把Listnode数组的头结点放入优先级队列中，通过堆排序得到最小值
for (ListNode head : lists) {
if (head != null) {
pq.add(head);
}
}
// 4. 连接合并链表
while (!pq.isEmpty()) {
// 4.1 将最小链表连接至合并链表
ListNode node = pq.poll();
tmp.next = node;
// 4.2 最小头结点已经被拿走，便判断该node链表是否有下一结点
// 如果有，那么把下一节点作为头结点放入优先级队列中
// 通过补充结点的操作，可以实现对所有结点的遍历
if (node.next != null) {
pq.add(node.next);
}
tmp = tmp.next;
}
return ret.next;
}
时间复杂度：优先队列 pq 中的元素个数最多是k，所以一次 poll 或者 add 方法的时间复杂度是O(logk)；所有的链表节点都会被加入和弹出 pq，所以算法整体的时间复杂度是O(Nlogk),其中k是链表的条数，N是这些链表的结点总数。
想要一次遍历就获得链表的中间结点，定义快慢指针。快指针的移动速度是慢指针的两倍，当快指针指向null时，慢指针到达中间结点。
注意：当链表的结点个数为偶数时，慢指针会指向中间靠后的结点。
public ListNode middleNode(ListNode head) {
// 1. 定义快慢指针
ListNode slow = head, fast = head;
// 2. 快指针的移动速度是慢指针的两倍，当快指针指向null时，慢指针到达中间结点。
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
5.倒数第k个结点
5.1 获取倒数第k个结点
只给你一个单链表的头结点，只允许一次遍历就获得倒数第k个结点，怎么做？
先定义一个fast结点，先走k步。
再定义一个slow结点，和fast结点一起走。当fast == null时，slow结点正好走到倒数第k个结点。
这样就获得了倒数第k个结点。
public ListNode findFromEnd(ListNode head, int n) {
// 1.1 先定义一个fast结点
ListNode slow = head, fast = head;
// 1.2 让fast先走k步
while (n != 0) {
fast = fast.next;
n--;
}
// 2. 再定义一个slow结点，和fast结点一起走。
// 当fast == null时，slow结点正好走到倒数第k个结点。
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
如果要删除单链表的倒数第k个结点，就要获取该结点的前一节点。如果当n=5时，就要得到头结点的前一结点，会发生空指针异常。因此要定义一个虚拟头结点，即避免了空指针的问题，同时能获得倒数第k个结点的前一节点。
public ListNode removeNthFromEnd(ListNode head, int n) {
// 1. 定义虚拟头结点
ListNode ret = new ListNode(-1);
ret.next = head;
// 2. 获得倒数第k个结点的前一节点
ListNode x = findFromEnd(ret, n + 1);
// 3. 删掉倒数第 n 个节点
x.next = x.next.next;
return ret.next;
}
public ListNode findFromEnd(ListNode head, int n) {
...
}
6.环形链表
6.1 判断链表是否包含环
同样用到了快慢双指针的思想。如果一个链表包含环，只要快指针比慢指针每次多走一步，那么最后快慢指针一定会相遇。
public class Solution {
public boolean hasCycle(ListNode head) {
// 1. 快慢指针初始化指向 head
ListNode slow = head, fast = head;
// 2. 快指针走到末尾时停止
while (fast != null && fast.next != null) {
// 3. 慢指针走一步，快指针走两步
slow = slow.next;
fast = fast.next.next;
// 4.1 快慢指针相遇，说明含有环
if (slow == fast) {
return true;
}
}
// 4.2 能走完循环，说明不含有环
return false;
}
}
怎么使用快慢指针解决呢？
第一张图：slow走了k步，那么fast一定走了2k步。那么k一定是环长度的倍数。
第二张图：设环起点到相遇点距离为m，所以起点到环起点距离为k-m。又因为k是环长度的倍数，所以环起点到相遇点距离为k-m。既然两者距离一样，那么让其中一个结点回到head结点，两者一样速度前进，相遇则遇到环起点。
public ListNode detectCycle(ListNode head) {
// 1. 定义快慢结点
ListNode slow = head, fast = head;
// 2. 是否是环形链表？如果不是，返回null；如果是，双结点相遇
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (fast == slow) {
break;
}
}
if (fast == null || fast.next == null) {
return null;
}
// 3. 寻找环起点
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
超绝思路：拼接链表，找到交点。如果没有交点，就把c1当成是null，一样可以通过。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 1. 定义pA、pB用于拼接
ListNode pA = headA, pB = headB;
// 2. 拼接链表，两结点一致则找到交点或为空
while (pA != pB) {
// p1 走一步，如果走到 A 链表末尾，转到 B 链表
if (pA != null) {
pA = pA.next;
} else {
pA=headB;
}
// p2 走一步，如果走到 B 链表末尾，转到 A 链表
if (pB != null) {
pB = pB.next;
} else {
pB = headA;
}
}
return pA;
}
反转链表
（1）迭代解法
第一种写法：
public ListNode reverseList(ListNode head) {
// 特殊情况
if (head == null || head.next == null) {
return head;
}
// 需要用的2+1个结点
ListNode pre = null, cur = head, nxt = cur.next;
while (cur != null) {
// 1. 反转，改变的是当前结点的前一结点
cur.next = pre;
// 2. 更新结点，如果不用nxt结点，cur无法更新
pre = cur;
cur = nxt;
if (nxt != null) {
nxt = nxt.next;
}
}
return pre;
}
第二种写法：
public ListNode reverseList(ListNode head) {
ListNode pre = null, cur = head;
while (cur != null) {
// 在循环内定义nxt，可以省略部分代码
ListNode nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
（2）递归解法
2.反转链表前N个结点
（1）迭代解法
ListNode reverseN(ListNode head, int n) {
if (head == null || head.next == null) {
return head;
}
ListNode pre = null, cur = head;
while (n > 0) {
// 另一种写法
ListNode nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
// 添加一个计数器
n--;
}
// head一直指向1结点，在他后面连上cur结点的当前位置就连接上整个链表
head.next = cur;
return pre;
}
（2）递归解法
public ListNode reverseBetween(ListNode head, int m, int n) {
if (m == 1) {
return reverseN(head, n);
}
// 找到第 m 个节点的前驱
// 采用计数器的时候需谨慎！！！
ListNode pre = head;
for (int i = 1; i < m - 1; i++) {
pre = pre.next;
}
// 从第 m 个节点开始反转
pre.next = reverseN(pre.next, n - m + 1);
return head;
}
private ListNode reverseN(ListNode head, int n) {
ListNode pre = null, cur = head;
while (n > 0) {
ListNode nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
n--;
}
head.next = cur;
return pre;
}
回文链表
public boolean isPalindrome(ListNode head) {
// 1. 找到链表中点
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if (fast != null) { // 奇偶链表的差异
slow = slow.next;
}
// 2. 中点左边是原链表，右边是从链表尾到链表中点的反转链表
ListNode left = head;
ListNode right = reverseN(slow); // 调用反转链表函数
// 3. 如果两链表值相同则为回文链表
while (right != null) {
if (left.val != right.val) {
return false;
}
left = left.next;
right = right.next;
}
return true;
}
private ListNode reverseN(ListNode head) { // 代码在前一节
ListNode pre = null, cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
二、顺序表相关算法
双指针
public int removeDuplicates(int[] nums) {
// 特殊情况
if (nums.length == 0) {
return 0;
}
// 1. 定义快慢指针
int slow = 0, fast = 0;
// 2. 在快指针指向数组范围内操作
while (fast < nums.length) {
// 2.2 当快慢指针数字不同时，覆盖原有数字
if (nums[slow] != nums[fast]) {
slow++;
nums[slow] = nums[fast];
}
// 2.1 当nums[slow] == nums[fast]时跳到下一个
fast++;
}
// 3. 返回唯一的个数为 slow + 1
return slow + 1;
}
public int removeElement(int[] nums, int val) {
// 1. 定义快慢指针
int slow = 0, fast = 0;
// 2. 在快指针指向数组范围内操作
while (fast < nums.length) {
// 2.2 当指针数字与val不同时，覆盖数字
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
// 2.1 当nums[fast] == val的时候跳到下一个
fast++;
}
return slow;
}
class Solution {
public void moveZeroes(int[] nums) {
// 1. 沿用上一题解，先把0全部去掉，其余顺序不变
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != 0) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
// 2. 最后把去掉的位置都填上0
for (; slow < nums.length; slow++) {
nums[slow] = 0;
}
}
}
2. 二分查找
int binarySearch(int[] nums, int target) {
// 一左一右两个指针相向而行
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = (right + left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1;
}
public int[] twoSum(int[] numbers, int target) {
// 1. 由于给定数组从下标1开始，则可以先按照正常下标运算，最后返回值+1即可
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
// 2.1 当和与目标数相等时，返回数组
if (sum == target) {
return new int[]{left + 1, right + 1};
}
// 2.2 当和比目标数小时，左边指针右移
else if (sum < target) {
left++;
}
// 2.3 当和比目标数大时，右边指针左移
else {
right--;
}
}
// 3. 不存在时的情况
return new int[]{-1, -1};
}
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while (left < right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}
5.回文串判断
public String longestPalindrome(String s) {
String ret = "";
// 1. 从第一个字符开始遍历，找到最长的回文字符串
for (int i = 0; i < s.length(); i++) {
// 2.1 有两种情况，可能是偶数个，也可能是奇数个
String a = palindrome(s, i, i);
String b = palindrome(s, i, i + 1);
// 2.2 既是奇数偶数的长度比较，同时也是每次遍历字符串的长度比较
ret = ret.length() > a.length() ? ret : a;
ret = ret.length() > b.length() ? ret : b;
}
return ret;
}
// 寻找最长回文字符串，指针从中间开始向左右扩散
private String palindrome(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
// 在这里，l和r由于判断逻辑会左右多走一步
// 由于substring的范围是[left, right)
// 因此最长回文字符串是s.substring(l + 1, r)
return s.substring(l + 1, r);
}
花式遍历
让你顺时针旋转二维数组，可以这么做：先以对角线旋转二维数组，再左右旋转。这样做巧妙的做到旋转二维数组。
public void rotate(int[][] matrix) {
// 以对角线旋转二维数组
int n = matrix.length;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) { // j为何等于i，而不是的等于0？
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
// 左右旋转数组
for (int[] arr : matrix) {
reverse(arr);
}
}
void reverse(int[] arr) {
int i = 0, j = arr.length - 1;
while (i < j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
如果是向左旋转二维数组，那么先以另一条对角线旋转二维数组，再左右旋转。
public static void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++) {
for (int j = n - i - 1; j >= 0; j--) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][n - 1 - i];]
matrix[n - 1 - j][n - 1 - i] = tmp;
}
}
for (int[] arr : matrix) {
reverse(arr);
}
}
public static void reverse(int[] arr) {
int i = 0, j = arr.length - 1;
while (i < j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
思路：设置4个变量，分别是左、右、上、下的边界。随着螺旋遍历，边界会逐渐缩小。
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int a = 0, b = n - 1;
int c = 0, d = m - 1;
List<Integer> list = new LinkedList<>();
while (list.size() < m * n) { // 遍历整个数组
if (c <= d) { // 如果上下边界在同一行，做最后一次遍历
for (int i = a; i <= b; i++) {
list.add(matrix[c][i]);
}
c++; // 上边界下移
}
if (a <= b) { // 如果左右边界在同一行，做最后一次遍历
for (int i = c; i <= d; i++) {
list.add(matrix[i][b]);
}
b--; // 右边界左移
}
if (c <= d) { // 同理
for (int i = b; i >= a; i--) {
list.add(matrix[d][i]);
}
d--; // 下边界上移
}
if (a <= b) { // 同理
for (int i = d; i >= c; i--) {
list.add(matrix[i][a]);
}
a++; // 左边界右移
}
}
return list;
}
参与讨论
(Participate in the discussion)
参与讨论