4507

im0use
QLW
BK-201_3

cc_xx

.梅子酒.

yxc

Kanam

CCSU_JP
runrunrun

1234_6

11天前

1.从尾到头打印链表

0≤ 链表长度 ≤1000。


/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> a;
{
}
reverse(a.begin(),a.end());
return a;
}
};


2.在O(1)时间删除链表结点,删除指定节点

/**
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
ListNode* newNode=new ListNode(-1);
newNode=node->next;
node->val=newNode->val;
node->next=newNode->next;

}
};


3.反转链表

/**
*
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode*pre=NULL;
while(cur)
{
ListNode*ne=cur->next;
cur->next=pre;
pre=cur;
cur=ne;
}
return pre;

}
};


/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
return tail;

}
};


4.反转链表中的某一段

5.合并两个排序的链表

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode*dummy = new ListNode(0);
ListNode*cur=dummy;

while(l1!=NULL&l2!=NULL)
{
if(l1->val<l2->val)
{
cur->next=l1;
l1=l1->next;
}
else
{
cur->next=l2;
l2=l2->next;
}
cur=cur->next;
}
if(l1!=NULL)
{
cur->next=l1;
}
else
{
cur->next=l2;
}
return dummy->next;
}
};


6.删除排序链表中的重复元素(I)

/**
* 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:
while(duyy!=NULL)
{
if(duyy->next!=NULL&&duyy->val==duyy->next->val)
{
duyy->next=duyy->next->next;
}
else
{
duyy=duyy->next;
}
}
}
};


7.删除排序链表中的重复元素(II)

(线性扫描)

O(n)

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode*dummy = new ListNode(-1);
ListNode*cur=dummy;
while(cur->next)
{
ListNode*go=cur->next;
while(go&&cur->next->val==go->val)go=go->next;
if(cur->next->next==go)cur=cur->next;
else cur->next=go;
}

return dummy->next;
}

};


8.链表中倒数第k个节点

k >= 1;

1.先将链表反转，循环链表一次
2.后有循环一次链表查找第k位

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* findKthToTail(ListNode* pListHead, int k) {
ListNode*pre=NULL;

while(cur)
{
ListNode*ne=cur->next;
cur->next=pre;
pre=cur;
cur=ne;
}
int i=1;

while(pre&&i<k)
{
pre=pre->next;
i++;
}
return pre;
}
};


9.两个链表的第一个公共结点

A：
····· a1 → a2
····· · ······ ↘
····················· c1 → c2 → c3
··················· · ↗
······ b1 → b2 → b3
B：

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:

while(p!=q)
{
if(p)
{
p=p->next;
}
else
{
}
if(q)
{
q=q->next;
}
else
{
}
}
return q;
}
};

class Solution {
public:
int lenA = 0, lenB = 0;
while (curA != NULL) { // 求链表A的长度
lenA++;
curA = curA->next;
}
while (curB != NULL) { // 求链表B的长度
lenB++;
curB = curB->next;
}
// 让curA为最长链表的头，lenA为其长度
if (lenB > lenA) {
swap (lenA, lenB);
swap (curA, curB);
}
// 求长度差
int gap = lenA - lenB;
// 让curA和curB在同一起点上（末尾位置对齐）
while (gap--) {
curA = curA->next;
}
// 遍历curA 和 curB，遇到相同则直接返回
while (curA != NULL) {
if (curA == curB) {
return curA;
}
curA = curA->next;
curB = curB->next;
}
return NULL;
}
};


10.设计链表

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

class MyLinkedList {
public:
struct ListNode
{
int val;
ListNode*next;
ListNode(int val):val(val),next(NULL){}
};
// 初始化链表
_dummyHead = new ListNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
_size = 0;
}
// index=0;是头节点(第一个节点)
int get(int index) {
if(index>_size-1||index<0)
{
return -1;
}
while(index--)
{
p=p->next;
}
return p->val;
}

ListNode*node = new ListNode(val);
_size++;
}

ListNode*node= new ListNode(val);
while(cur->next)
{
cur=cur->next;
}
cur->next=node;
_size++;
}

void addAtIndex(int index, int val) {
ListNode*node=new ListNode(val);
if(index>_size)return;
while(index--)
{
cur=cur->next;
}
node->next=cur->next;
cur->next=node;
_size++;
}

void deleteAtIndex(int index) {
if(index>=0&&index<_size)
{
while(index--)
{
cur=cur->next;
}
ListNode* tmp = cur->next;
cur->next = cur->next->next;//若只单纯留这一句，这多余的节点还在内存中没删除，消耗多余内存
delete tmp;
_size--;
}
}
// 打印链表
while (cur->next != nullptr) {
cout << cur->next->val << " ";
cur = cur->next;
}
cout << endl;
}
private:
int _size;
};

/**
* int param_1 = obj->get(index);
* obj->deleteAtIndex(index);
*/


11.链表中环的入口结点

QQ截图20181202023846.png

[1, 2, 3, 4, 5, 6]
2

slow总共走了2x+y步，fast总共走了2x+2y+x步（理想情况），所以两个指针总共走了 5x+3y 步

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
while(slow!=fast)
{
slow=slow->next;
fast=fast->next;
}
return fast;
}
}
return NULL;
}
};

//判断是否有环:
class Solution {
public:
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
return true;
}
}
return false;
}
};


12.两两交换链表中的节点

O(n)，其中 n是链表的节点数量。需要对每个节点进行更新指针的操作。

/**
* 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*dummy=new ListNode(0);
ListNode*cur = dummy;
while(cur->next&&cur->next->next)
{
ListNode*tmp1=cur->next;
ListNode*tmp2=cur->next->next->next;

cur->next=cur->next->next;
cur->next->next=tmp1;
cur->next->next->next=tmp2;

cur=cur->next->next;
}
return dummy->next;
}
};


13 移除链表元素

/**
* 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* removeElements(ListNode* head, int val) {
ListNode*dummy=new ListNode(-1);
ListNode*cur = dummy;
while(cur->next)
{
if(cur->next->val==val)
{
cur->next=cur->next->next;
}
else
{
cur=cur->next;
}

}
return dummy->next;
}
};


14.删除链表的倒数第N个节点

1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

O(n)

class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode*dummy = new ListNode(-1);
ListNode*slow=dummy;
ListNode*fast=dummy;

while(n--)
{
fast=fast->next;
}
while(fast->next)
{
fast=fast->next;
slow=slow->next;
}
ListNode*tmp=slow->next;
slow->next=tmp->next;
delete tmp;
return dummy->next;

}
};


15.链表中倒数第k个节点

O(n)


class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {

while(k--)
{
fast=fast->next;
}
while(fast)         //为什么这里变为fast->next就不可以呢，因为若只有三个元素,k=3,此时k已经变成了null,如何判断null的下一//个,所以出现错误,不行,但使用虚拟节点开头就可以,因为始终多一个点,k不能超过链表的节点(不包括虚拟节//点的数量)
{
slow=slow->next;
fast=fast->next;
}
return slow;
//  ListNode*dummy = new ListNode(-1);
// ListNode*slow=dummy;
// ListNode*fast=dummy;

// while(k--)
// {
//     fast=fast->next;
// }
// while(fast->next)
// {
//     fast=fast->next;
//     slow=slow->next;
// }
// return slow->next;
}
};


16.链表求和

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode*dummy1=new ListNode(-1);
ListNode*dummy2=new ListNode(-1);
ListNode*dummy3=new ListNode(-1);
dummy1->next=l1;
dummy2->next=l2;

ListNode*cur1=dummy1;
ListNode*cur2=dummy2;
ListNode*cur3=dummy3;

int t=0;
while(cur1->next!=NULL||cur2->next!=NULL||t)
{
if(cur1->next)t+=cur1->next->val;
if(cur2->next)t+=cur2->next->val;
ListNode*node=new ListNode(t%10);
t=t/10;
cur3->next=node;
cur3=cur3->next;
//细节
if(cur1->next)
{
cur1=cur1->next;
}
if(cur2->next)
{
cur2=cur2->next;
}
}
return dummy3->next;
}
};


17.链表求和II

/**
* 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> cur1,cur2;
ListNode*dummy=new ListNode(-1);
while(l1)
{
cur1.push(l1->val);
l1=l1->next;
}
while(l2)
{
cur2.push(l2->val);
l2=l2->next;
}

int t=0;
while(!cur1.empty()||!cur2.empty()||t)
{
if(!cur1.empty())t+=cur1.top();
if(!cur2.empty())t+=cur2.top();
ListNode*node =new ListNode(t%10);
t/=10;
if(!cur1.empty())cur1.pop();
if(!cur2.empty())cur2.pop();
// cur->next=node;
// cur=cur->next;  这样拿到的链表还需反转才能得到正确答案，因为是倒着存的, 因此要倒着输出
node->next=dummy->next; //头插法,即反转了一遍
dummy->next=node;
}
return dummy->next;
}
};


18.合并两个链表

O(n)

class Solution {
public:
ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
ListNode*dummy=new ListNode(-1);
dummy->next=list1;
ListNode*cur=dummy;

for(int i=0;i<a;i++)
{
cur=cur->next;
}
// 此时cur指向a索引节点的前驱节点

for(int i=a;i<=b;i++)
{
cur->next=cur->next->next;
}
ListNode*dummy1=new ListNode(-1);
dummy1->next=list2;
ListNode*ne=dummy1;
while(ne->next)
{
ne=ne->next;
}
ne->next=cur->next;
cur->next=dummy1->next;
return dummy->next;
}
};


19.交换链表中的节点

/**
* 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* swapNodes(ListNode* head, int k) {
ListNode*dummy=new ListNode(-1);
ListNode*fast=dummy;
ListNode*slow=dummy;
ListNode*change=dummy;
for(int i=0;i<k;i++)
{
change=change->next;
fast=fast->next;
}
while(fast->next)
{
slow=slow->next;
fast=fast->next;
}
slow=slow->next;
swap(slow->val,change->val);
return dummy->next;
}
};


2个月前
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

const int N = 110;
int q[N];

int main()
{
int a,b,c,d;
cin>>a>>b>>c>>d;

for(int i=a;i<b;i++)
{
q[i]++;
}
for(int i=c;i<d;i++)
{
q[i]++;
}
int sum=0;
for(int i=0;i<=N;i++)
{
if(q[i]!=0)
{
sum++;
}

}
cout<<sum;
return 0;
}


2个月前
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x, y; cin>>x>>y;
int ans=0, dist=1, d=1;
//dist: 距离
//d: 方向(1向右 -1向左)
while(1)
{
if((d==1 && x<=y && y<=x+dist) || (d==-1 && y<=x && x<=y+dist))
{
//找到了Bessie
ans+=abs(y-x);
cout<<ans;
break;
}
//没有找到Bessie
else dist*=2, ans+=dist, d*=-1;
}
return 0;
}



2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


2个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~