Day4 链表剩下的基本操作
Lc24
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
//画个图，弄个新节点，然后按照顺序进行连接，最主要的是连的时候思路要清晰
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead=new ListNode(0);
dummyHead->next=head;
ListNode* cur=dummyHead;
while(cur->next!=nullptr&&cur->next->next!=nullptr){
ListNode *temp1=cur->next;
ListNode *temp2=cur->next->next->next;
cur->next=cur->next->next;
cur->next->next=temp1;
cur->next->next->next=temp2;
cur=cur->next->next;
}
return dummyHead->next;
}
};
Lc19 删除链表倒数第n个元素，注意审题，一开始写成了显示倒数第n个元素，另外注意让快指针多走一步，这样方便慢指针直接删除元素。
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *dummyNode=new ListNode(0);
dummyNode->next=head; //每次自定义完记得让dummynode指向头节点
ListNode *pre=dummyNode;
ListNode *cur=dummyNode;
while(n--&&cur!=NULL){
cur=cur->next;
}
cur=cur->next; //让快指针再多走一步，这样
while(cur){
cur=cur->next;
pre=pre->next;
}
pre->next=pre->next->next;
return dummyNode->next;
}
};
///链表相交的题目，不知道为啥leetcode一直过不了，不理解。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode * curA= headA;
ListNode * curB= headB;
int lenA,lenB=0;//求一下两个链表的长度
while(curA!=NULL){
lenA++;
curA=curA->next;
}
while(curB!=NULL){
lenB++;
curB=curB->next;
}
curA=headA;
curB=headB;
if(lenB>lenA){
swap(curA,curB);//保证永远是A最大
swap(lenA,lenB);
}
int gap=lenA-lenB;
while(gap--){
curA=curA->next;
}
while(curA!=NULL){
if(curA==curB){
return curA;
}
curA=curA->next;
curB=curB->next;
}
return NULL;
}
};
环的进阶问题，实际上仔细思考很有意思 Lc142
首先是如何哦判断链表是否有环，这个很简单，就是快慢指针同时出发，如果相遇的话说明有环，如果没相遇的话说明无环。其次是判断环的相遇位置：这个就比较有意思了，直接让一个指针从当前位置出发，一个指针从头出发，他们第一次相遇的位置一定是环相遇的位置，也就是x=z
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *fast=head;
ListNode *slow=head;
while(fast!=NULL&&fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
if(fast==slow){
ListNode *index1=fast;
ListNode *index2=head;
while(index1!=index2){
index1=index1->next;
index2=index2->next;
}
return index2;
}
}
return NULL;
}
};