链表的几类关键问题
1.双指针操作: 快慢指针/左右指针
2.中间节点操作
3.反转/合并/插入/删除
4.环判断
5.组合操作
双指针
详情见 TwoPointer 的一个章节
快慢指针找中间节点
如何找到链表的中间节点? 用快慢指针同时前进, 慢指针之前的位置 pre 作为搜索 index; 具体又分为两种情况, 一种是奇数链表, 一种是偶数链表
[0,2,3,4,5]
[0,2,3,4,5,6]
ListNode* findMidNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
Listnode* pre; // pre 相比 slow 少走一步
while (fast != nullptr && fast->next != nullptr) {
pre = head;
slow = slow->next;
fast = fast->next->next;
}
// 对于奇数链表来说
// slow 返回的是中间节点 2
// pre 返回的是中间节点的上一个节点 1
// 对于偶数链表来说
// slow 返回的是 后一个中间节点 3
// pre 返回的是 前一个中间几点 2
}
206.反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：输入：head = [1,2] 输出：[2,1]
示例 3：输入：head = [] 输出：[]
分析:
1.迭代:
反转的核心操作, 是要把当前的节点指向它前一个节点, 但是我们得迭代, 所以需要先记下来它前一个是谁和后一个是谁, 然后执行迭代操作更新, 因此就是用三个指针 pre, cur, next 这3个就能完成
原始状态 1 -> 2 -> 3 -> nullptr
目标状态 nullptr <- 1 <- 2 <- 3, 假设我们要操作 2 这个节点的反转 1 -> 2 -> 3 得到 1 <- 2 -> 3, 关键操作是将当前的节点反向指向它的前一个节点, 也就是cur -> next = pre, 同时为了能迭代我们首先要记下来下一个节点, 然后再实施关键翻转操作
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* pre = nullptr;
ListNode* cur = head;
ListNode* next = nullptr;
while (cur != nullptr) {
next = cur->next; // 先记下来它下一个是谁, 不然反转完当前之后, 没法走到下一个反转流程
cur->next = pre; // 执行核心的反转操作
pre = cur; // 执行迭代
cur = next; // 执行迭代
}
return pre;
}
};
2.递归操作
想一下假设只有一个节点需要反转, 后面的都已经反转好了, 就差一步大功告成, 应该怎么反转?
1 -> [2 -> 3 -> 4 -> nullptr]
1 -> [nullptr <- 2 <- 3 <- 4] 此时 newHead 指向4 让 1->next->next 指向1
1 <- [2 <- 3 <- 4] 得到左边的结果, 但还差一步 1->next = nullptr
nullptr <- 1 <- [2 <- 3 <- 4]
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
};
92.反转链表II
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]
示例 2：输入：head = [5], left = 1, right = 1 输出：[5]
分析:
1.如果找到原始的起止点之后, 然后再反转, 相当于需要扫描两次, 我们需要某种方式, 使得翻转操作只需要做一次就能完成
2.可以采用向后扫描, 对第二个元素采用 [头插] 的操作, 例如对于 [1,2,3,4,5], 有
[1,2,3,4,5]
[1,3,2,4,5]
[1,4,3,2,5]
3.如何实现对于整个区间内的 [区间内头插法反转] 操作, 需要用到三个指针
cur: 维护的是反转区域内的第1个节点, 也就是反转完之后的最后一个节点, 在上面例子里面就是 2, 这个节点只操作反转过程, cur 指针始终不动
pre: 当前反转区域内的上一个节点, 在上面例子里面就是1, pre指针始终不动
next: next 节点执行头插的操作, 也就是把 next 节点每次放到区间开头, 每次把 next 节点拉到 pre->next, 全部翻转完毕后 next 迭代找到下一个 cur->next
假设对于 1->2->3->4->5, 我们想要反转 2 到 5 这个区间, 这个区间反转第一个元素是3搞到最前, 得到 1->3->2->4->5
pre = 1 cur = 2 next = 3
cur->next = next->next;
先把要插入的隔过去 1->2->4->5 保持原样 3->4->5
next->next = pre->next;
把插入到头部的元素拉到前面 3->2->4->5 保持原样 1->2->4->5
pre->next = next;
建立 pre 和头插之后结果的关系 1->3->2->4->5
next = cur->next
更新迭代指针
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummy = new ListNode(-1, head);
ListNode* pre = dummy;
// 移动 pre 到指向区间前一个节点
for (int i = 0; i < left - 1; ++i) {
pre = pre->next;
}
ListNode* cur = pre->next; // cur 节点是反转区域第1个节点, 也是反转区域最后一个节点, 始终不动
ListNode* next; // next 是要执行头插的节点, 每次移动到反转区域的第1个元素, 并一直迭代
for (int i = 0; i < right - left; ++i) {
next = cur->next; // 找到头插节点
cur->next = next->next; // 隔过去待头插入的节点
next->next = pre->next; // 执行头插: 插入头节点到区间第1个节点
pre->next = next; // 链接 pre -> 头插元素
}
return dummy->next;
}
};
25.K 个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。示例 1：输入：head = [1,2,3,4,5], k = 2 输出：[2,1,4,3,5]
示例 2：输入：head = [1,2,3,4,5], k = 3 输出：[3,2,1,4,5]
分析:
1.应用 [区间内头插法] 的操作可以对任意区间进行反转, 我们只需要对多个区间采取相同的操作; 每个 [区间内头插法] 操作完成之后, 我们将 pre 和 cur 顺序往下移动一个区间, 再下一个区间进行 [区间内头插法]
2.先求出来区间的总长度; 然后一个区间一个区间地做 [区间内头插法]
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (head == nullptr || head->next == nullptr) {
return head;
}
int len = 0;
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* t = head;
while (t) {
++len;
t = t->next;
}
ListNode* pre = dummy;
ListNode* cur = pre->next;
ListNode* next;
while (len >= k) {
for (int i = 1; i < k; ++i) {
next = cur->next;
cur->next = next->next;
next->next = pre->next;
pre->next = next;
}
pre = cur;
cur = pre->next;
len -= k;
}
return dummy->next;
}
};
148.排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：输入：head = [4,2,1,3] 输出：[1,2,3,4]
示例 2：输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]
示例 3：输入：head = [] 输出：[]
分析:
1.采用分治 (归并) 的方法, 每次先找到链表的中点, 强行断开, 然后执行归并排序
2.每次找中点的时候, 用快慢指针找中点, 注意这里的中点是偏小的那一个, 也就是 slow 前面的 pre 指针, 这样比较适合前后断开的操作
3.合并的时候, 执行的是两个有序链表的合并操作
4.归并排序的思路 + 快慢指针找中点 + 有序链表合并之后可以完成该操作
class Solution {
public:
ListNode* findMidNode(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* slow = head;
ListNode* fast = head;
ListNode* pre;
while (fast != nullptr && fast->next != nullptr) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
return pre;
}
ListNode* mergeSortedList(ListNode* list1, ListNode* list2) {
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
ListNode* p1 = list1;
ListNode* p2 = list2;
while (p1 != nullptr && p2 != nullptr) {
if (p1->val < p2->val) {
cur->next = p1;
p1 = p1->next;
} else {
cur->next = p2;
p2 = p2->next;
}
cur = cur->next;
}
cur->next = (p1 != nullptr) ? p1 : p2;
ListNode* ret = dummy->next;
delete dummy;
return ret;
}
ListNode* sortList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* p1 = head;
ListNode* mid = findMidNode(head);
ListNode* p2 = mid->next;
mid->next = nullptr;
p1 = sortList(p1);
p2 = sortList(p2);
ListNode* ans = mergeSortedList(p1, p2);
return ans;
}
};
1265.逆序打印不可变链表
给您一个不可变的链表，使用下列接口逆序打印每个节点的值：
ImmutableListNode: 描述不可变链表的接口，链表的头节点已给出。
您需要使用以下函数来访问此链表（您 不能 直接访问 ImmutableListNode）：
ImmutableListNode.printValue()：打印当前节点的值。
ImmutableListNode.getNext()：返回下一个节点。
输入只用来内部初始化链表。您不可以通过修改链表解决问题。也就是说，您只能通过上述 API 来操作链表。示例 1：输入：head = [1,2,3,4] 输出：[4,3,2,1]
示例 2：输入：head = [0,-4,-1,3,-5] 输出：[-5,3,-1,-4,0]
示例 3：输入：head = [-2,0,6,4,4,-6] 输出：[-6,4,4,6,0,-2]
分析:
1.采用递归的思想去倒序遍历
/**
* // This is the ImmutableListNode's API interface.
* // You should not implement it, or speculate about its implementation.
* class ImmutableListNode {
* public:
* void printValue(); // print the value of the node.
* ImmutableListNode* getNext(); // return the next node.
* };
*/
class Solution {
public:
void printLinkedListInReverse(ImmutableListNode* head) {
if (head == nullptr) return;
printLinkedListInReverse(head->getNext());
head->printValue();
return;
}
};
234.回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：输入：head = [1,2,2,1] 输出：true
示例 2：输入：head = [1,2] 输出：false
分析:
1.找到链表的中点, 然后反转后半部分, 用半部分和后半部分遍历, 先准备个反转链表和找到中点的操作, 反转链表写递归的更快, 找到中点可以用快慢指针
class Solution {
public:
ListNode* reverse(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* newHead = reverse(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
ListNode* findMidNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
bool isPalindrome(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return true;
}
ListNode* mid = findMidNode(head);
ListNode* p1 = head;
ListNode* p2 = reverse(mid);
while (p1 != nullptr & p2 != nullptr) {
if (p1->val != p2->val) {
return false;
}
p1 = p1->next;
p2 = p2->next;
}
return true;
}
};
2.两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。示例 1：输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.
示例 2：输入：l1 = [0], l2 = [0] 输出：[0]
示例 3：输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]
分析:
1.纯模拟实现, 注意各种进位的判断, 可以先处理两个链表同时有节点的情况, 再单独处理一个链表有节点的情况, 然后再处理最后的一个进位的情况
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
ListNode* p1 = l1;
ListNode* p2 = l2;
int sum = 0;
int data = 0;
int carry = 0;
while (p1 && p2) {
sum = p1->val + p2->val + carry;
data = sum % 10;
carry = sum / 10;
ListNode* tmp = new ListNode(data);
cur->next = tmp;
p1 = p1->next;
p2 = p2->next;
cur = cur->next;
}
ListNode* p = (p1) ? p1 : p2;
while (p) {
sum = p->val + carry;
data = sum % 10;
carry = sum / 10;
p->val = data;
cur->next = p;
cur = cur->next;
p = p->next;
}
if (carry > 0) {
ListNode* finalNode = new ListNode(carry);
cur->next = finalNode;
cur = cur->next;
}
return dummy->next;
}
};
24.两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：输入：head = [] 输出：[]
示例 3：输入：head = [1] 输出：[1]
分析:
1.这个题意是想让我们按照每两个一组交换节点, 需要画图在纸上才能看清楚指针的变动顺序
2.先设置一个 dummy, dummy->next = head:
3.我们尝试反转第一组, 因为需要一个前置节点才能开始连接, 因此声明一个 pre, 一开始 pre = dummy
先取出来 node1 和 node2
pre->next = node2;
node1->next = node2->next;
node2->next = node1;
pre = node1;
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(-1, head);
ListNode* pre = dummy;
while (pre->next != nullptr && pre->next->next != nullptr) {
ListNode* node1 = pre->next;
ListNode* node2 = pre->next->next;
pre->next = node2;
node1->next = node2->next;
node2->next = node1;
pre = node1;
}
ListNode* ans = dummy->next;
delete dummy;
return ans;
}
};
138.随机链表的复制
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。例如，如果原链表中有 X 和 Y 两个节点，其中 X.random —> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random —> y 。 返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。示例 1： 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2： 输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]
示例 3： 输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]
分析:
1.如果没有随机指针, 我们遍历复制就行, 因为有随机指针的存在, 当我们想复制某个节点的时候, 它的随机指针指向的那个节点可能还没创建, 因此不太好复制.
2.这里有个非常巧妙的办法, 先复制在拆分, 对于链表 a->b->c, 我们可以在每个元素之后先建一个a->a’->b->b’->c->c’, 然后我们对所有a’和b’和c’找到随机指针指向的节点是它原来节点的随机指针指向的节点对应的后继节点, 然后重新遍历一遍, 按照 [原来节点] 和 [复制节点] 拆分出来; 因为随机指针可以指向空值, 给复制节点找随机指针指向的结点的时候, 需要判断一下能否指向一个节点
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if (head == nullptr) {
return nullptr;
}
Node* p = head;
// 先复制串联镜像节点 a->a'->b->b'->c->c
while (p != nullptr) {
Node* node = new Node(p->val);
node->next = p->next;
p->next = node;
p = node->next;
}
p = head;
Node* cp = nullptr;
// 给复制节点们找到对应的随机指针的正确指向
while (p != nullptr) {
cp = p->next;
if (p->random != nullptr) {
cp->random = p->random->next;
}
p = cp->next;
}
p = head;
cp = head->next;
Node* newHead = cp;
// p 和 cp 各自串自己的糖葫芦
while (cp->next != nullptr) {
p->next = cp->next;
p = p->next;
cp->next = p->next;
cp = cp->next;
}
p->next = nullptr;
return newHead;
}
};
转载请注明来源, from goldandrabbit.github.io
