138. 复制带随机指针的链表
o(1)的空间复杂度
/*
// 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) {
auto h=head;
while(h)
{
auto tmp=new Node(h->val); //复制新结点在原结点的后面
tmp->next=h->next;
h->next=tmp;
h=tmp->next;
}
for(auto h=head;h;h=h->next->next)
{
if(h->random)h->next->random=h->random->next;//将新结点的rand指针赋值，指向原结点rand指针指向的后面一个结点
}
auto dummy=new Node(-1),p=dummy;
for(auto h=head;h;h=h->next)
{
auto t=h->next;//将链表拆开
p->next=t;
p=p->next;
h->next=t->next;
}
return dummy->next;
}
};
o(n)空间复杂度：哈希
/*
// 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) {
unordered_map<Node*,Node*>mp;
for(auto h=head;h;h=h->next)
{
auto cur=new Node(h->val);
mp[h]=cur;
}
for(auto h=head;h;h=h->next)
{
mp[h]->next=mp[h->next];
mp[h]->random=mp[h->random];
}
return mp[head];
}
};
19. 删除链表的倒数第 N 个结点
完整链表：
#include<bits/stdc++.h>
using namespace std;
struct ListNode
{
int val;
ListNode *next;
ListNode():val(0),next(nullptr){}
ListNode(int x):val(x),next(nullptr){}
ListNode(int x,ListNode * next):val(x),next(next){}
};
ListNode* creat(int n)
{
ListNode *dummy=new ListNode(-1);
ListNode *p=dummy;
while(n--)
{
int x;
scanf("%d",&x);
ListNode *h=new ListNode(x);
p->next=h;
p=p->next;
}
return dummy->next;
}
ListNode* removeNthFromEnd(ListNode* head, int n)
{
auto dummy=new ListNode(-1);
dummy->next=head;
auto first=dummy,second=dummy;
for(int i=1;i<=n;i++)first=first->next;
while(first->next)
{
first=first->next;
second=second->next;
}
second->next=second->next->next;
return dummy->next;
}
int main()
{
int n;
scanf("%d",&n);
ListNode *dummy=creat(n);
int k;
scanf("%d",&k);
removeNthFromEnd(dummy,k);
auto p=dummy;
while(p)
{
if(p->next)printf("%d->",p->val);
else printf("%d",p->val);
p=p->next;
}
return 0;
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
auto dummy=new ListNode(-1);
dummy->next=head;
auto first=dummy,second=dummy;//创建两个虚拟节点，第一个节点先走n步，然后两个结点一起走，两个节点相差n步，第一个结点走到最后一步时，第二个结点等于要删除的结点的前一个结点
while(n--)first=first->next;
while(first->next)
{
first=first->next;
second=second->next;
}
second->next=second->next->next;
return dummy->next;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
*(node)=*(node->next);//把当前的整个空间的值复制成下一个节点的整个空间的值
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
node->val=node->next->val;
node->next=node->next->next;//对于单链表，要删除当前节点必须知道前一个结点，将当前结点变成下一个结点，再删除下一个结点，相当于删除了当前结点
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head)return head;
auto tmp=head;
while(tmp->next)
{
if(tmp->next->val==tmp->val)tmp->next=tmp->next->next;
else tmp=tmp->next;
}
return head;
}
};
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(!head)return head;
auto dummy=new ListNode(-1);
dummy->next=head;
int cnt=0;
for(auto h=head;h;h=h->next)cnt++;
k%=cnt;
auto first=dummy,second=dummy;
while(k--)
{
first=first->next;
}
while(first->next)
{
first=first->next;
second=second->next;
}
first->next=dummy->next;
dummy->next=second->next;
second->next=NULL;
return dummy->next;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(!head)return head;
auto dummy=new ListNode(-1);
dummy->next=head;
auto p=dummy;
while(p->next&&p->next->next)
{
auto tmp=p->next->next;
p->next->next=tmp->next;
tmp->next=p->next;
p->next=tmp;
p=p->next->next;
}
return dummy->next;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(!head)return head;
auto dummy=new ListNode(-1);
dummy->next=head;
auto p=dummy;
while(p->next&&p->next->next)
{
auto a=p->next,b=a->next;
p->next=b;
a->next=b->next;
b->next=a;
p=a;
}
return dummy->next;
}
};
/**
* 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)return head;
auto a=head,b=head->next;
while(b)
{
auto c=b->next;
b->next=a;
a=b;
b=c;
}
head->next=NULL;
return a;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if(left==right)return head;
auto dummy=new ListNode(-1);
dummy->next=head;
auto p=dummy;
int cnt=left-1;
while(cnt--)p=p->next;
auto a=p->next,b=a->next;
for(int i=1;i<=right-left;i++)
{
auto c=b->next;
b->next=a;
a=b;
b=c;
}
p->next->next=b;
p->next=a;
return dummy->next;
}
};
160. 相交链表
解法一：o(n)空间
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
unordered_map<ListNode*,int>mp;
while(headA)
{
mp[headA]=1;
headA=headA->next;
}
while(headB)
{
if(mp[headB]==1)return headB;
headB=headB->next;
}
return NULL;
}
};
o(1)空间
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
auto a=headA,b=headB;
while(a!=b)
{
if(a==NULL)a=headB;
else a=a->next;
if(b==NULL)b=headA;
else b=b->next;
}
return a;
}
};
142. 环形链表 II
环的长度等于x+y
快慢指针：蓝色慢指针，红色快指针
我的臭代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
auto fast=head,slow=head;
int f=0;
while(fast)
{
if(!f)
{
if(fast->next)fast=fast->next->next;
else return NULL;
slow=slow->next;
}
else
{
fast=fast->next;
slow=slow->next;
}
if(f==0&&fast==slow)
{
slow=head;
f=1;
}
if(f==1&&fast==slow)return fast;
}
return NULL;
}
};
y总优雅的代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
auto fast=head,slow=head;
while(fast)
{
fast=fast->next;
slow=slow->next;
if(fast)fast=fast->next;
else return NULL;
if(fast==slow)
{
slow=head;
while(slow!=fast)slow=slow->next,fast=fast->next;
return fast;
}
}
return NULL;
}
};
148. 排序链表
递归所用的空间是和递归层数有关的，不是o(1)的，需要o(log(n))的空间
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
int n=0;
for(auto h=head;h;h=h->next)n++;
auto dummy=new ListNode(-1);
dummy->next=head;
for(int i=1;i<n;i*=2)
{
auto cur=dummy;
for(int j=0;j+i<n;j+=i*2)
{
auto left=cur->next,right=cur->next;
for(int k=1;k<=i;k++)right=right->next;
int l=0,r=0;
while(l<i&&r<i&&right)
{
if(left->val<=right->val)
{
cur->next=left;
cur=left;
left=left->next;
l++;
}
else
{
cur->next=right;
cur=right;
right=right->next;
r++;
}
}
while(l<i)
{
cur->next=left;
cur=left;
left=left->next;
l++;
}
while(r<i&&right)
{
cur->next=right;
cur=right;
right=right->next;
r++;
}
cur->next=right;
}
}
return dummy->next;
}
};
