1.交换链表

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

前后指针实现

1.没有元素或者只有一个元素无意义

2.给出一个前驱prev，以及用来交换的两个节点cur和next

3.我当时是这么想的，如果两个指针一起动，那么就要用cur和next同时判断结束，也许这个条件会比较苛刻(我就烦这种边界条件)，所以我觉得动一个指针来判断条件就可以了

4.所以我选择用cur判断，在循环中确定next的指向；prev和cur的更新

5.判断条件就变成了cur是否为空，cur的next是否为空

6.循环进去说明需要交换，所以确定next的指向是cur的next；确定是否更新的是根节点；交换；更新prev，cur进入下一轮

class Solution {
public:ListNode* swapPairs(ListNode* head) {if(head==nullptr||head->next==nullptr)return head;ListNode* prev = nullptr;ListNode* cur = head;ListNode* next = head;while(cur&&cur->next){next=cur->next;if(prev==nullptr)head=next;elseprev->next=next;cur->next=next->next;next->next=cur;prev=cur;cur=cur->next;}return head;}
};

前驱？前驱！触发被动了一样的字眼，我是不是可以用递归做啊🤔

 递归交换

1.首先没有元素或者只有一个元素无意义，过

2.递归函数，确定参数头节点要传，因为会换；前驱next、cur和后继next

3.我们依然可以用一个节点进行判断是否到链表底部，cur是否空或者cur的next为空 -- 对应的就是链表是双数还是单数

4.往下传递归的参数其实只需要更新cur和prev，因为前驱必须确定下来，不然往下找不到了，cur也必须有因为我们的底部条件是靠cur判断的，prev等于现在的cur->next，cur等于cur->next->next，就是都得跨两个节点

5.执行交换的代码，next自然就是cur->next。先看是否需要更新的是头节点其条件是prev是否为nullptr；随后交换，返回即可

class Solution {
public:void _swapR(ListNode*& head,ListNode* prev,ListNode* cur,ListNode* next){if(cur==nullptr||cur->next==nullptr)return;_swapR(head,cur->next,cur->next->next,next);next=cur->next;if(prev==nullptr)head=next;elseprev->next=next;cur->next=next->next;next->next=cur;return;}ListNode* swapPairs(ListNode* head) {if(head==nullptr||head->next==nullptr)return head;_swapR(head,nullptr,head,head);return head;}
};

2. 快慢指针

我觉得代码实现很简单，主要是思想

想要找从后往前的数，就应该用快慢指针，先让快的指针走n次，然后快慢指针一起动，快指针到边界，慢指针的下一个就是我们要删除的节点。

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* slow = head;ListNode* fast = head;for(int i=0;i<n;i++)fast=fast->next;if(fast==nullptr){ListNode* tmp = slow;head = slow->next;delete tmp;return head;}while(fast->next){slow=slow->next;fast=fast->next;}ListNode* tmp = slow->next;slow->next=tmp->next;delete tmp;return head;}
};

3.链表相交

面试题 02.07. 链表相交

因为只想时间复杂度为O(N)，空间复杂度为O(1)

所以我想的是给他们的长度算出来，做差值，然后长的那个往后走差值个数，这样两个链表同样一个长度往下走，那么只要知道什么时候两个节点地址一样，就返回

class Solution {
public:int getListNum(ListNode* root){int num = 0;while(root){root=root->next;num++;}return num;}ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {int NA = getListNum(headA);int NB = getListNum(headB);int gap = abs(NA-NB);ListNode* more = headA;ListNode* less = headB;if(NA<NB){less = headA;more = headB;}for(int i=0;i<gap;i++){more=more->next;}while(less!=nullptr&&more!=nullptr&&more!=less){more=more->next;less=less->next;}return more;}
};

4.环形链表

142. 环形链表 II

哈希表 嘻哈表

讲个笑话，程序员在课本上学到了数据冲突可以用哈希表解决；到面试时，面试官问这个求职的程序员：“当程序员和项目经理发生冲突时要怎么解决”，“使用哈希表”程序员想都没想脱口而出。

使用哈希表可以直观的看到数据是否之前插入过，使用起来很简单，不过哈希表通过红黑树实现的这个背后逻辑才是关键，这里不说明了

class Solution {
public:ListNode *detectCycle(ListNode *head) {set<ListNode*> s;ListNode* cur = head;while(cur){if(s.find(cur)!=s.end())return cur;s.insert(cur);cur=cur->next;}return nullptr;}
};

快慢指针

操场上一个跑得快一个跑得慢，最终快的一定会把慢的套圈。这个题目的思路也是一样的

1.定义快慢指针，快指针走两个节点，慢指针走一个节点；其实可以如果真的有环，慢指针不动，快指针以一个节点为单位靠近慢指针

2.只要两个地址碰到一起，那确实是有环，不过题目要我们返回头一个链接上的节点，所以我们需要通过一个数学思想来解决

 最后得到x = (n - 1) (y + z) + z，说明x跟z长度一样

那么从fast和从头节点同时走，会遇到一样的节点

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* cur = head;ListNode* fast = head;int fastnum = 0;ListNode* slow = head;int slownum = 0;while(fast&&fast->next&&fast->next->next){fast=fast->next->next;fastnum+=2;slow=slow->next;slownum++;if(slow==fast){while(cur!=fast){cur=cur->next;fast=fast->next;}return cur;}}return nullptr;}
};