LeetCode-链表
链表（Linked List）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针（Pointer）。
由于不必须按顺序存储，链表在插入的时候可以达到 O(1)O(1) 的复杂度，比另一种线性表 —— 顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n)O(n) 的时间，而顺序表相应的时间复杂度分别是 O(log\ n)O(log n) 和 O(1)O(1)。
对于链表相关的问题，应该注意以下几点：
头节点的使用，即dummyNode的使用，可以减少边界条件判断。涉及到头节点的操作，比如可能删除head等等，使用dummyNode可以减少判断。最后返回dummyNode.next
创建新的节点时，注意在栈上分配对象，如果使用new 需要delete。ps：后续一些题解没有及时更正该方面的问题。
-
快慢指针。多用于寻找中间节点等，衍生问题环形链表等。主要在于在O(N)的时间来快速获取到想要的节点。
使用快慢指针查找中间节点时，当fast和slow都指向head和slow指向head，fast指向head->next 获取到的中间节点及边界条件不一致，需要注意。
cut函数，cut(ListNode* node,int k) 将链表前k个值切割，返回第k+1个node；多用于分隔链表。
反转链表，需要pre=null,cur=head,next 三个指针， 每次进行更新，最后返回pre。
合并链表，注意dummyNode的使用以及边界判空。
删除节点，删除当前节点，可以将下个节点的值复制给当前节点，并指向下下个节点。另一种思路时需要找到删除节点的前驱。
时间复杂度，可以考虑一些辅助工作，如map，stack，set等。
另一个就是链表和排序算法以及树的遍历的结合。归并排序，dfs等等。可以等后续章节进行分析。
链表相关的问题也可以考虑递归的方式进行解决。从而简化问题。
下面介绍LeetCode常见的链表问题。
1.反转链表
206.反转链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head==NULL || head->next==NULL){
return head;
}
ListNode* pre=NULL;
ListNode* cur=head;
ListNode* next;
while(cur){
next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}
return pre;
}
};
92.反转链表II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (head==NULL || head->next==NULL){
return head;
}
ListNode* pre=NULL;
ListNode* cur=head;
ListNode* next;
while(m>1){
pre=cur;
cur=cur->next;
m--;
n--;
}
// 需要记录下pre 和 tail；即反转后的头节点和尾节点
ListNode* con = pre; //反转后的头节点
ListNode* tail=cur; // 反转后的尾节点
while(n>0){
next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
n--;
}
if(con){
con->next=pre; //进行连接
}else{
head=pre; //此时证明从第一个节点开始反转，那么头节点直接就是反转后的头节点
}
tail->next=cur; //尾节点的next设置为下一个节点cur
return head;
}
};
2.删除元素
237.删除链表中的节点
class Solution {
public:
void deleteNode(ListNode* node) {
//struct ListNode* tmp=node->next;
node->val=node->next->val;
node->next=node->next->next;
//delete tmp;
}
};
203.移除链表元素
删除链表中等于给定值 *val* 的所有节点。
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if(head==NULL){
return NULL;
}
struct ListNode* t=new ListNode(-1);
t->next=head;
struct ListNode* pre=t;
while(pre->next!=NULL){
if (pre->next->val==val){
auto s=pre->next;
pre->next=pre->next->next;
delete s;
}else{
pre=pre->next;
}
}
return t->next;
}
};
19.删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(head==NULL || head->next==NULL){
return NULL;
}
ListNode* first=head;
ListNode* second=head;
int i=0;
// 先走n步，找到需要删除的pre节点。
while(i<n){
first=first->next;
i++;
}
//主要为了判断是否是删除首元素
if(!first){
return head -> next;
}
while(first->next!=NULL){
first=first->next;
second=second->next;
}
ListNode* tmp=second->next;
second->next=second->next->next;
delete tmp;
return head;
}
};
83.删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* cur=head;
while(cur!=NULL &&cur->next!=NULL){
if(cur->next->val==cur->val){
cur->next=cur->next->next;
}else{
cur=cur->next;
}
}
return head;
}
};
82.删除排序链表中的重复元素II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
提示：需要两个指针；一个用来遍历，另一个用来删除。
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode dummyNode(-1);
ListNode* pre=&dummyNode;
ListNode* cur=head;
ListNode* tmp;
int n,val;
while(cur){
tmp = cur;
for(n=0,val=cur->val;cur!=NULL && cur->val==val;++n){
cur=cur->next;
}
if (n==1){
pre->next=tmp;
pre=pre->next;
}
}
pre->next=NULL;
return dummyNode.next;
}
};
1171.从链表中删去总和值为0的连续节点
给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。删除完毕后，请你返回最终结果链表的头节点。
你可以返回任何满足题目要求的答案。（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）
提示：我们可以考虑如果给的入参不是链表是数组的话，只需要求出前缀和，对于前缀和相同的项，那他们中间的部分即是可以消除掉的，比如以 [1, 2, 3, -3, 4] 为例，其前缀和数组为 [1, 3, 6, 3, 7] ，我们发现有两项均为 3，则 6 和 第二个 3 所对应的原数组中的数字是可以消掉的。换成链表其实也是一样的思路，把第一个 3 的 next 指向第二个 3 的 next 即可。
示例 1：
输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。
class Solution {
public:
ListNode* removeZeroSumSublists(ListNode* head) {
// 求和，当出现重复是 证明两个重复节点之间的数据可以被删除；
// 然后继续递归； 返回值为dummy->next；
if (head==NULL){
return head;
}
ListNode dummy(0);
dummy.next=head;
ListNode* dummyPtr=&dummy;
map<int,ListNode*> map;
map[0]=dummyPtr;
int sum=0;
while(head!=NULL){
sum+=head->val;
if(map.find(sum)!=map.end()){
map[sum]->next=head->next;
return removeZeroSumSublists(dummy.next);
}else{
map[sum]=head;
head=head->next;
}
}
return dummy.next;
}
};
3.合并链表
合并链表，需要注意头节点dummyNode的使用。另外为了降低复杂度，可以考虑使用归并算法。
21.合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy = ListNode(-1); // 创建栈空间对象即可。
ListNode* prev = &dummy; // 注意这里需要取地址&
while(l1 != NULL && l2 != NULL) {
if(l1->val <= l2->val) {
prev->next = l1;
l1 = l1->next;
} else {
prev->next = l2;
l2 = l2->next;
}
prev = prev->next;
}
prev->next = l1 != NULL ? l1 : l2;
return dummy.next;
}
};
23.合并K个有序链表
题解：已经实现了合并两个有序链表了，那么其实可以使用归并的思想进行合并k个链表，两两合并，时间复杂度为Nlogk
ListNode* mergeKLists(vector<ListNode*>& lists) {
int len = lists.size();
if(len < 1) return NULL;
while(len>1){
int m = (len + 1) / 2;
for(int i=0;i<m && i+m < len;++i){
lists[i] = mergeTwoLists(lists[i],lists[i+m]);
}
len = m;
}
return lists[0];
}
2. 两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
题解：新的节点等与两个节点的(val+进位)%10; 下一轮的进位为(val+进位)/10；
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *root=new ListNode(0);
ListNode *cur=root;
ListNode *tmp;
int c=0;
while(l1!=NULL || l2!=NULL || c!=0){ //注意边界条件，可能最后只有进位，需要创建新的节点
int v1=l1?l1->val:0;
int v2=l2?l2->val:0;
int sum=v1+v2+c;
c=sum/10;
tmp=new ListNode(sum%10);
cur->next=tmp;
cur=tmp;
if (l1){
l1=l1->next; // 注意边界条件
}
if (l2){
l2=l2->next;
}
}
return root->next;
}
};
445.两数相加II
给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶:如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例:
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7
题解：当当前值的计算依赖下一项的计算时，可以使用递归的方法来实现回溯。当前值=（val+下一项的进位）/10。需要两个链表等长。 另一种办法是借助额外的结构，来实现。例如栈/数组等。
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
vector<ListNode*> l1v,l2v;
to_vector(l1,l1v);
to_vector(l2,l2v);
int i=l1v.size()-1, j=l2v.size()-1;
int d = 0;
ListNode *head = NULL;
while(i >= 0 || j >= 0){
if(i >= 0) d += l1v[i--]->val;
if(j >= 0) d += l2v[j--]->val;
ListNode* p = new ListNode(d%10);
p->next = head;
head = p;
d /= 10;
}
if(d) {
ListNode* p = new ListNode(d);
p->next = head;
head = p;
}
return head;
}
void to_vector(ListNode* a,vector<ListNode*>& v){
while(a){
v.push_back(a);
a = a->next;
}
}
};
4.重排链表
链表按照指定的规则进行重新排序。比如首尾相连，交换链表节点等等。
24.两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
题解：声明dummyNode，pre指向dummy。 start指向1，end指向2. 让pre.next=end;start.next=end.next;end.next=start. pre此刻再向前移动到start。
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode pre = new ListNode(0);
pre.next = head;
ListNode temp = pre;
while(temp.next != null && temp.next.next != null) {
ListNode start = temp.next;
ListNode end = temp.next.next;
temp.next = end;
start.next = end.next;
end.next = start;
temp = start;
}
return pre.next;
}
}
25. k个一组反转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例 :
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
题解：合理利用cut函数，每k个一组，切割成链表，然后反转，然后注意进行链接。每次反转前判断下长度是否达到k。当对头节点有进行操作是，注意使用dummyNode。 主要要保持链表直接的连接。
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode dummyHead(0);
dummyHead.next=head;
auto cur=dummyHead.next;
auto tail = &dummyHead;
while(cur){
auto left = cur;
cur = cut(left, k); // left->@->@ right->@->@->@...
tail->next = reverseList(left,k);
while(tail->next){
tail=tail->next;
}
}
return dummyHead.next;
}
// k个一组进行反转，采用cut函数，连接的时候，注意保证尾部正确。
ListNode* cut(ListNode* head,int k){
auto p=head;
while(--k && p){
p=p->next;
}
if(!p){
return nullptr;
}
auto next=p->next;
p->next=nullptr;
return next;
}
ListNode* reverseList(ListNode* head,int k) {
struct ListNode* p=head;
while(p!=NULL){
p=p->next;
k--;
}
if (k>0){
return head;
}
struct ListNode* pre=NULL;
struct ListNode* cur=head;
struct ListNode* tmp=NULL;
while(cur){
tmp=cur->next;
cur->next=pre;
pre=cur;
cur=tmp;
}
return pre;
}
};
61.旋转链表
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
题解：方法一：先连接，再旋转。再断开。方法二：可以先整体逆序，然后前k个逆序，后n-k个逆序。
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(head==NULL){
return NULL;
}
if (head->next==NULL){
return head;
}
ListNode *cur=head;
int n=1;
while(cur->next!=NULL){
cur=cur->next;
n++;
}
cur->next=head;
ListNode *new_tail = head;
int i=0;
for(i=0;i<n - k % n - 1;++i){
new_tail=new_tail->next;
}
ListNode* tmp=new_tail->next;
new_tail->next=NULL;
return tmp;
}
};
143.重排链表
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
经典问题：考察快慢指针找中间节点；分隔链表；链表反转，链表合并。需要考虑将中间节点分配到第一个链表还是第二个链表。考虑清楚边界条件。
class Solution {
public:
void reorderList(ListNode* head) {
// 先快慢指针找到中间节点，然后对后面的反转，最后合并
if(head==NULL || head->next==NULL){
return ;
}
ListNode* slow=head;
ListNode* fast=head->next;
while(fast!=NULL && fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
}
ListNode* l2=slow->next;
slow->next=NULL;
ListNode* l1=head;
// 反转list2
ListNode* pre=NULL;
ListNode* cur=l2;
ListNode* next;
while(cur!=NULL){
next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}
l2=pre;
// 合并l1 l2
while(l2!=NULL){
slow=l1->next;
fast=l2->next;
l1->next=l2;
l2->next=slow;
l1=slow;
l2=fast;
}
return;
}
};
147.链表进行插入排序
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode h(-1);
h.next = head;
ListNode* pre = &h;
ListNode* cur = head;
ListNode* lat;
ListNode* tmp;
while (cur != NULL) {
lat = cur->next; // 记录下一个要插入排序的值
if (lat != NULL && lat->val < cur->val) {
// 只有 cur.next 比 cur 小才需要向前寻找插入点
while (pre->next != NULL && pre->next->val < lat->val) {
pre = pre->next; // 继续向后移动
}
// 找到要插入的位置，此时 pre 节点后面的位置就是 lat 要插入的位置
tmp = pre->next;
pre->next = lat;
cur->next = lat->next;// 保证cur不断
lat->next = tmp;
pre = &h;// 由于每次都是从前往后找插入位置，所以需要每次插入完成后要让 pre 复位
} else {
// 都这直接把 cur 指针指向到下一个
cur = lat;
}
}
return h.next;
}
};
148.排序链表
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
题解：要求时间复杂度，考虑到归并排序。两两合并，需要logn次。每次进行n个比较。需要注意的点；cut函数实现，合并链个有序链表；dummyNode使用；链表的连接；等等。
class Solution {
public:
ListNode* sortList(ListNode* head) {
ListNode dummyHead(0);
dummyHead.next=head;
auto p=head;
int length=len(p);
for (int size=1;size<length;size<<=1){
auto cur=dummyHead.next;
auto tail = &dummyHead;
while(cur){
auto left = cur;
auto right = cut(left, size); // left->@->@ right->@->@->@...
cur = cut(right, size); // left->@->@ right->@->@ cur->@->..
tail->next = merge(left, right);
while(tail->next){
tail=tail->next;
}
}
}
return dummyHead.next;
}
int len(ListNode *p){
int length=0;
while (p) {
++length;
p = p->next;
}
return length;
}
ListNode* cut(ListNode* head,int n ){
auto p=head;
while(--n && p){
p=p->next;
}
if(!p){
return nullptr;
}
auto next=p->next;
p->next=nullptr;
return next;
}
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode dummyHead(0);
auto p = &dummyHead;
while (l1 && l2) {
if (l1->val < l2->val) {
p->next = l1;
p = l1;
l1 = l1->next;
} else {
p->next = l2;
p = l2;
l2 = l2->next;
}
}
p->next = l1 ? l1 : l2;
return dummyHead.next;
}
};
5.分隔链表
86.分隔链表
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
题解：分解成两个链表，再连接。注意dummyNode的使用。
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if (head==NULL ||head->next==NULL){
return head;
}
ListNode l_head(-1);
ListNode r_head(-1);
ListNode* l=&l_head;
ListNode* r=&r_head;
auto l_tmp=l;
auto r_tmp=r;
while(head!=NULL){
if(head->val<x){
l->next=head;
l=l->next;
}else{
r->next=head;
r=r->next;
}
head=head->next;
}
l->next=r_tmp->next;
r->next=NULL;
return l_tmp->next;
}
};
109.有序链表转换二叉搜索树
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
题解：二叉搜索树的前序遍历为有序数组。那么对于链表中间节点即为跟节点。采用递归进行遍历即可。
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
//核心思想，中心节点就是根节点，递归构造左右子节点。
if(head==NULL){
return NULL;
}
ListNode* mid=getMidNode(head);
TreeNode* node=new TreeNode(mid->val);
if (head==mid){
return node;
}
node->left=sortedListToBST(head);
node->right=sortedListToBST(mid->next);
return node;
}
// 查找中间节点并返回。并分割left链表最后指向NULL。
ListNode* getMidNode(ListNode *head){
ListNode* pre=NULL;
ListNode* slow=head;
ListNode* fast=head;
while(fast!=NULL && fast->next!=NULL){
pre=slow;
slow=slow->next;
fast=fast->next->next;
}
if (pre!=NULL){
pre->next=NULL;
}
return slow;
}
};
725.分隔链表
给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。
每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。
这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。
返回一个符合上述规则的链表的列表。
举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]
示例 1：
输入:
root = [1, 2, 3], k = 5
输出: [[1],[2],[3],[],[]]
解释:
输入输出各部分都应该是链表，而不是数组。
例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。
示例 2：
输入:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解释:
输入被分成了几个连续的部分，并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。
class Solution {
public:
vector<ListNode*> splitListToParts(ListNode* root, int k) {
// 遍历root的长度，得到len。
// if len<=k ; 那么每个都是独立节点，再增加k-len个空节点。
// if len>k; 那么切分为 len/k 个片段；其中 前 len%k个片段，长度为 len/k + 1;
// 实现cut(ListNode* head,int k); 切割前k个节点，返回第k+1个节点后的链表
// 循环切割，时间复杂度为O(N)
vector<ListNode*> vec;
ListNode* cur=root;
int len=getLen(root);
if (len<k){
for(int i=0;i<k;i++){
vec.push_back(cur);
cur=cut(cur,1);
}
}else{
int step=len/k;
int m=len%k;
int i=0;
for (i=0;i<m;i++){
vec.push_back(cur);
cur=cut(cur,step+1);
}
for(i=m;i<k;i++){
vec.push_back(cur);
cur=cut(cur,step);
}
}
return vec;
}
int getLen(ListNode* head){
if(head==NULL){
return 0;
}
int len=0;
ListNode* cur=head;
while(cur){
cur=cur->next;
len++;
}
return len;
}
ListNode* cut(ListNode* head,int k){
while(k>1 && head){
head=head->next;
k--;
}
if (head==NULL){
return NULL;
}
ListNode* tmp=head->next;
head->next=NULL;
return tmp;
}
};
6.使用额外结构降低时间复杂度
138.复制带随机指针的链表
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深拷贝。
题解：先全部复制一遍，再进行指针关联
class Node {
public:
int val;
Node* next;
Node* random;
Node() {}
Node(int _val, Node* _next, Node* _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public:
// hash 空间复杂O(N)
// 原地复制 空间复杂O(1) 复制节点 复制random 拆链表
Node* copyRandomList(Node* head) {
if(head==nullptr){
return nullptr;
}
map<Node*,Node*> map;
Node* cur=head;
while(cur){
map[cur]=new Node(cur->val,nullptr,nullptr);
cur=cur->next;
}
cur=head;
while(cur){
map[cur]->next=map[cur->next];
map[cur]->random=map[cur->random];
cur=cur->next;
}
return map[head];
}
};
817.链表组件
给定一个链表（链表结点包含一个整型值）的头结点 head。
同时给定列表 G，该列表是上述链表中整型值的一个子集。
返回列表 G 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 G 中）构成的集合。
示例 1：
输入:
head: 0->1->2->3
G = [0, 1, 3]
输出: 2
解释:
链表中,0 和 1 是相连接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一个组件，同理 [3] 也是一个组件，故返回 2。
示例 2：
输入:
head: 0->1->2->3->4
G = [0, 3, 1, 4]
输出: 2
解释:
链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。
class Solution {
public:
int numComponents(ListNode* head, vector<int>& G) {
set<int> m_set;
for (int i=0;i<G.size();i++){
m_set.insert(G[i]);
}
ListNode* cur=head;
int num = 0;
while(cur){
if(m_set.find(cur->val)!= m_set.end() && (cur->next==NULL || m_set.find(cur->next->val)== m_set.end())){
num++;
}
cur=cur->next;
}
return num;
}
};
1019.链表中下一个更大节点
给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。
每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。
返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。
注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。
示例 1：
输入：[2,1,5]
输出：[5,5,0]
示例 2：
输入：[2,7,4,3,5]
输出：[7,0,5,5,0]
示例 3：
输入：[1,7,5,1,9,2,5,1]
输出：[7,9,9,9,0,5,0,0]
class Solution {
public:
//题解，使用栈先进后出。找到第一个比较大的就更新对应的数组值。
vector<int> nextLargerNodes(ListNode* head) {
int count = 0; //计数，作为下标
vector<int> result;
stack<pair<int, int>> tmp; //first为val，second为下标
while (head)
{
result.push_back(0); //给result数组后面+0，1为保证长度，2是默认值（后无更大的值的话）为0
while (!tmp.empty() &&
head->val > tmp.top().first) //栈不为空且head指针的val值大于栈顶的元素的值
{
result[tmp.top().second] = head->val; //result数组修改，满足题意要求的最大值，然后出栈，继续循环
tmp.pop();
}
tmp.push(make_pair(head->val, count++)); //count++计数
head = head->next; //下一个节点
}
return result;
}
};
7.快慢指针
160.相交链表
编写一个程序，找到两个单链表相交的起始节点。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int aLen=0;
int bLen=0;
ListNode *curA=headA;
ListNode *curB=headB;
while(curA!=NULL){
curA=curA->next;
aLen++;
}
while(curB!=NULL){
curB=curB->next;
bLen++;
}
int i=0;
curA=headA;
curB=headB;
if (aLen>bLen){
for(i=0;i<aLen-bLen;i++){
curA=curA->next;
}
}else{
for(i=0;i<bLen-aLen;i++){
curB=curB->next;
}
}
while(curA){
if(curA==curB){
return curA;
}else{
curA=curA->next;
curB=curB->next;
i++;
}
}
return NULL;
}
};
234.回文链表
请判断一个链表是否为回文链表。
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(head==NULL||head->next==NULL){
return true;
}
ListNode* slow=head;
ListNode* fast=head->next;
while(fast!=NULL && fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
}
ListNode* r=resver(slow->next);
while(r!=NULL){
if(r->val!=head->val){
return false;
}
r=r->next;
head=head->next;
}
return true;
}
ListNode* resver(ListNode* head){
if(head==NULL||head->next==NULL){
return head;
}
ListNode* pre=NULL;
ListNode* cur=head;
ListNode* next;
while(cur!=NULL){
next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}
return pre;
}
};
328.奇偶链表
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
示例 2:
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
说明:
应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if(head==NULL||head->next==NULL){
return head;
}
ListNode* t1=head;
ListNode* t2=head->next;
ListNode* t2head=t2; //必须先保存，才可以保证链接。因为后续head->next 变了。
while(t2!=NULL && t2->next!=NULL){
t1->next=t2->next;
t1=t1->next;
t2->next=t1->next;
t2=t2->next;
}
t1->next=t2head;
return head;
}
};
