一轮的算法训练完成后,对相关的题目有了一个初步理解了,接下来进行专题训练,以下这些题目就是汇总的高频题目
题目题干直接给出对应博客链接,这里只给出简单思路、代码实现、复杂度分析
反转链表
依据难度等级分别为反转链表、区间反转链表、K个一组反转链表,【算法训练-链表 一】【反转链表】反转链表、区间反转链表、K个一组反转链表
反转链表【EASY】
LeetCode地址,双指针移动逐个扭转指针方向,关键词:双指针,临时节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
// 1 入参校验,如果链表为空或者只有一个节点,直接返回
if (head == null || head.next == null) {
return head;
}
// 2 定义双指针节点进行遍历反转操作
ListNode pre = null;
ListNode cur = head;
// 3 遍历链表,进行反转操作
while (cur!= null) {
// 1 定义临时节点存储当前节点的下一个节点
ListNode pNext = cur.next;
// 2 当前节点断开指向上一个节点
cur.next = pre;
// 3 双指针向前移动
pre = cur;
cur = pNext;
}
// 4 返回尾节点,也就是新的头节点
return pre;
}
}
时间复杂度:O(N),遍历了一遍链表
空间复杂度:O(1), 额外使用了常数级的指针变量
区间反转链表【MID】
LeetCode地址,双指针到指定位置就位,然后进行区间内的反转操作,关键词:双指针,临时节点,虚拟头节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
// 1 入参校验,如果链表为空或者只有一个节点,直接返回
if (head == null || head.next == null) {
return head;
}
// 如果整数left和right相等或者left大于right,直接返回
if (left == right || left > right) {
return head;
}
// 2 定义虚拟头节点与双指针,如果头节点也被反转了就丢了,所以需要虚拟头节点
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode pre = dummyHead;
ListNode cur = head;
// 3 双指针同时向前left-1步走到修改位置
for (int i = 1; i < left; i++) {
cur = cur.next;
pre = pre.next;
}
// 4 双指针开始在区间内进行反转操作1-2-3-4-5
for (int i = left; i < right; i++) {
// 记录节点3
ListNode pNext = cur.next;
// 节点2指向节点4
cur.next = pNext.next;
// 节点3指向节点2
pNext.next = pre.next;
// 节点1指向节点3 : 1-3-2-4-5, cur一直指向节点2,pre一直指向节点1,下一轮4和3-2整体交换
pre.next = pNext;
}
// 5 返回区间反转后的链表
return dummyHead.next;
}
}
时间复杂度:O(N),遍历了一遍链表
空间复杂度:O(1), 额外使用了常数级的指针变量
K个一组反转链表【HARD】
LeetCode地址,递归的将区间进行反转然后进行拼接,关键词:双指针,递归
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// 1 入参校验,如果链表为空或者只有一个节点或者k小于2,直接返回
if (head == null || head.next == null || k < 2) {
return head;
}
// 2 设置区间尾节点等于头节点
ListNode tail = head;
for (int i = 0; i < k; i++) {
// 如果tail为空,说明链表长度小于k,无需反转,直接返回这段子区间的头节点
if (tail == null) {
return head;
}
// 如果tail不为空,tail指针向前移动,移动k步,直到移动到下一区间头节点
tail = tail.next;
}
// 3 对区间进行反转操作,返回新的头节点
ListNode newHead = reverse(head, tail);
// 4 反转后,head变成了当前区间尾节点,tail作为下一子区间头节点传入方法递归,区间连接
head.next = reverseKGroup(tail, k);
// 5 返回新的头节点
return newHead;
}
// 区间反转链表
private ListNode reverse(ListNode head, ListNode tail) {
// 1 入参判断,如果链表为空或者只有一个节点,直接返回
if (head == null || head.next == null) {
return head;
}
// 2 定义双指针节点进行遍历反转操作
ListNode pre = null;
ListNode cur = head;
// 3 遍历链表,进行反转操作,tail为下一区间的头节点,所以这里是cur != tail
while (cur != tail) {
// 记录当前节点的下一个节点
ListNode pNext = cur.next;
// 当前节点断开指向上一个节点
cur.next = pre;
// 双指针向前移动
pre = cur;
cur = pNext;
}
// 4 返回尾节点,也就是新的头节点
return pre;
}
}
时间复杂度:O(N),虽然递归反转,但链表只遍历了一遍
空间复杂度:O(N/K)*O(1)
,递归的最大栈深度,也就是递归深度 *每次递归的空间复杂度
合并链表
依据难度分为合并两个有序链表以及合并K个有序链表,【算法训练-链表 二】【合并链表】合并两个有序链表、合并K个有序链表
合并两个有序链表【EASY】
LeetCode地址,主要思路就是双指针在两个有序链表上漫游,将较小的依次补全到新的链表上,关键词:双指针
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 1 入参校验,如果链表为空直接返回
if (list1 == null && list2 == null) {
return null;
}
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
// 2 定义虚拟头节点和两个漫游指针
ListNode dummyHead = new ListNode(-1);
ListNode p1 = list1;
ListNode p2 = list2;
ListNode p = dummyHead;
// 3 双指针分别在两个链表漫游
while (p1 != null && p2 != null) {
// 1 下一个节点挂p1
if (p1.val <= p2.val) {
p.next = p1;
p1 = p1.next;
} else {
// 2 下一个节点挂p2
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
// 4 如果其中一个链表空了则挂另一个链表
if (p1 == null) {
p.next = p2;
}
if (p2 == null) {
p.next = p1;
}
// 5 返回头结点
return dummyHead.next;
}
}
时间复杂度:O(N+M),分别对两个链表进行了遍历
空间复杂度:O(1), 额外使用了常数级的指针变量
合并K个有序链表【HARD】
LeetCode地址,应用分治的思想,先将K个有序链表进行划分,然后两两合并,关键词:双指针,分治
划分完子问题,子问题处理完返回到上一层级
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return divideMerge(lists, 0, lists.length-1);
}
// 划分子问题
private ListNode divideMerge(ListNode[] lists, int left, int right) {
// 1 终止条件,划分到最后的单个链表
if (left > right) {
return null;
}
// 2 划分到最小单个链表直接返回
if (left == right) {
return lists[left];
}
// 3 合并两个链表
int mid = left + (right - left) / 2;
return mergeTwoLists(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right));
}
// 合并两个有序链表
private ListNode mergeTwoLists(ListNode pHead1, ListNode pHead2) {
// 1 入参校验,如果链表为空直接返回
if (pHead1 == null && pHead2 == null) {
return null;
}
if (pHead1 == null) {
return pHead2;
}
if (pHead2 == null) {
return pHead1;
}
// 2 定义虚拟头节点和两个漫游指针
ListNode dummyHead = new ListNode(-1);
ListNode p1 = pHead1;
ListNode p2 = pHead2;
ListNode cur = dummyHead;
// 3 双指针分别在两个链表漫游
while (p1 != null && p2 != null) {
// 1 下一个节点挂p1
if (p1.val <= p2.val) {
cur.next = p1;
p1 = p1.next;
} else {
// 2 下一个节点挂p2
cur.next = p2;
p2 = p2.next;
}
cur = cur.next;
}
// 4 如果其中一个链表空了则挂另一个链表
if (p1 == null) {
cur.next = p2;
}
if (p2 == null) {
cur.next = p1;
}
// 5 返回头结点
return dummyHead.next;
}
}
时间复杂度:O(NLogN),二分分治进行了LogN次划分,每次遍历时间复杂度为O(N)
空间复杂度:O(LogN), 递归栈深度为LogN
链表查找
依据难度为:查找链表中倒数第K个节点,【算法训练-链表 六】【链表查找】:链表中倒数第k个节点
链表中倒数第k个节点【EASY】
LeetCode地址,解题思路就是应用快慢指针,快指针先于慢指针K步,然后同时移动,这样快指针到达链表尾部,慢指针刚好在倒数第K个节点,关键词:快慢指针
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
// 1 入参校验如果head为空或者cnt小于1,返回head
if (head == null || head.next == null || cnt < 1) {
return head;
}
// 2 定义快慢指针都指向头结点
ListNode fast = head;
ListNode slow = head;
// 3 快指针先前进cnt步
for (int i = 1; i < cnt; i++) {
// fast为null,证明给的用例cnt大于链表总长度,返回null
if (fast == null) {
return null;
}
fast = fast.next;
}
// 4 快慢指针同时前进,当快指针为尾节点时,慢指针位置就是倒数第K个
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
// 5 返回slow的位置
return slow;
}
}
时间复杂度:O(N),遍历了一遍链表
空间复杂度:O(1), 额外使用了常数级的指针变量