1.移除链表元素
就是续签prenode curnode 需要注意本地使用虚拟头节点逻辑更加简单
/**
* 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* removeElements(ListNode* head, int val) {
ListNode* dummyHead = new ListNode();
dummyHead->next=head;
ListNode* prenode= dummyHead;
ListNode* curnode= dummyHead->next;
while(curnode!=nullptr){
if(curnode->val==val){
ListNode* delenode=curnode;
prenode->next=curnode->next;
curnode=curnode->next;
delete delenode;
}else{
prenode=curnode;
curnode=curnode->next;
}
}
auto result = dummyHead->next;
delete dummyHead;
return result;
}
};
2.设计链表
class MyLinkedList {
public:
struct mynode{
int val;
mynode * next;
mynode():val(0),next(nullptr){}
};
MyLinkedList() {
dummyHead=new mynode();
}
int get(int index) {
mynode* cur = dummyHead;
for(int i=0;i<=index;i++){
cur=cur->next;
if(cur==nullptr){
break;
}
}
// cout<<"after:index::"<<index<<endl;
if(cur==nullptr){
return -1;
}
return cur->val;
}
void addAtHead(int val) {
mynode *newHead=new mynode();
newHead->val=val;
newHead->next= dummyHead->next;
dummyHead->next =newHead;
}
void addAtTail(int val) {
// pre结点和cur结点同时移动直到cur是空节点 直接在pre后面插入即可
mynode *prenode=dummyHead;
mynode *curnode=dummyHead->next;
while(curnode!=nullptr){
prenode=curnode;
curnode=curnode->next;
}
mynode *tailnode=new mynode();
tailnode->val = val;
prenode->next=tailnode;
}
void addAtIndex(int index, int val) {
// 这里先判断index是否有效 然后pre和cur同时移动index个步数即可
mynode * cur = dummyHead->next;
int maxindex=-1;
while(cur!=nullptr){
maxindex++;
cur=cur->next;
}
if(maxindex+1<index){
return;
}
mynode* prenode = dummyHead;
mynode* curnode = dummyHead->next;
while(index--){
prenode=curnode;
curnode=curnode->next;
}
mynode *newnode=new mynode();
newnode->val = val;
newnode->next=prenode->next;
prenode->next=newnode;
}
void deleteAtIndex(int index) {
if(get(index)==-1){
return;
}
mynode* pre = dummyHead;
mynode* cur = dummyHead->next;
while(index--){
pre=cur;
cur=cur->next;
}
mynode* deletnode = cur;
pre->next=cur->next;
delete deletnode;
}
// 使用虚拟头结点 方便插入删除
mynode * dummyHead=nullptr;
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/
3.反转链表
主要思路 使用虚拟有节点 然后遍历每个节点 直接插入头部即可
/**
* 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* reverseList(ListNode* head) {
ListNode* dummyHead = new ListNode();
dummyHead->next=nullptr;
ListNode* cur = head;
while(cur!=nullptr){
ListNode* nextnode = cur->next;
cur->next=dummyHead->next;
dummyHead->next=cur;
cur=nextnode;
}
ListNode* result = dummyHead->next;
delete dummyHead;
return result;
}
};
4.两两交换链表中的节点
使用虚拟头结点 找到pre 然后取 待交换的两个节点
ListNode* nextnode1=pre->next;
ListNode* nextnode2=pre->next->next;
另外注意 交换之后 pre更新位置不是两个节点的下一个节点 而是
pre=nextnode1;
/**
* 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) {
ListNode* dummyHead = new ListNode();
dummyHead->next=head;
ListNode* pre=dummyHead;
while(pre->next!=nullptr && pre->next->next!=nullptr){
ListNode* nextnode1=pre->next;
ListNode* nextnode2=pre->next->next;
ListNode* tempnode=nextnode2->next;
nextnode2->next=nextnode1;
nextnode1->next=tempnode;
pre->next=nextnode2;
pre=nextnode1;
}
ListNode* result=dummyHead->next;
delete dummyHead;
return result;
}
};
/**
* 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) {
ListNode* dummyhead = new ListNode();
dummyhead->next = head;
ListNode *slow=dummyhead;
ListNode *fast=dummyhead;
while(n--){
// 快指针先走n个节点
fast=fast->next;
if(fast==nullptr){
break;
}
}
if(fast==nullptr){
// 证明n已经大于节点个数 无意义
delete dummyhead;
return head;
}
while(fast->next!=nullptr){
slow=slow->next;
fast=fast->next;
}
ListNode *delenode=slow->next;
slow->next=delenode->next;
delete delenode;
ListNode * result = dummyhead->next;;
delete dummyhead;
return result;
}
};
6.链表相交
主要思路：
方法一：首先长的链表先移动差值个单位 然后 然后判断两个链表此时位置是否是同一个节点 不是的话一起一个单位 再次判断 还不是的话 再次移动 如此反复判断 直到其中一个链表移动到末尾即可。
/**
* 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) {
int lenA =0;
ListNode *curA=headA;
while(curA){
lenA++;
curA=curA->next;
}
int lenB =0;
ListNode *curB=headB;
while(curB){
lenB++;
curB=curB->next;
}
// cur1指向更长的
ListNode * cur1=headA;
ListNode * cur2=headB;
int k = abs(lenA-lenB);
if(lenA<lenB){
swap(cur1,cur2);
}
while(k--){
cur1=cur1->next;
}
while(cur1!=nullptr){
if(cur1==cur2){
return cur1;
}else{
cur1=cur1->next;
cur2=cur2->next;
}
}
return nullptr;
}
};
方法二：
/**
* 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) {
ListNode *curA= headA;
ListNode *curB= headB;
while(curA!=curB){
curA=curA==NULL?headB:curA->next;
curB=curB==NULL?headA:curB->next;
}
return curA;
}
};
7.环形链表II
注意
快慢指针都是从第一个节点出发
ListNode *slow=head;
ListNode *fast=head;
循环体内慢指针每次走一个节点 快指针每次走两个节点
slow = slow->next;
fast=fast->next->next;
如果快慢指针不相遇一直这么走 直到fastnullptr或者fast->nextnullptr结束 相遇的话 直接重新设置两个指针 一个从头节点出发 一个从相遇节点出发 每次比较 如果不是同一个节点 每次都走一个节点长度 直到相遇即可
ListNode *cur1=head;
ListNode *cur2=slow;
while(cur1!=cur2){
cur1=cur1->next;
cur2=cur2->next;
}
return cur1;
完整代码如下
/**
* 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) {
ListNode *slow=head;
ListNode *fast=head;
while(fast!=nullptr&&fast->next!=nullptr){
slow = slow->next;
fast=fast->next->next;
if(fast==slow){
ListNode *cur1=head;
ListNode *cur2=slow;
while(cur1!=cur2){
cur1=cur1->next;
cur2=cur2->next;
}
return cur1;
}
}
return nullptr;
}
};