【数据结构】链表常见题目

链表

合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/

1.定义一个哨兵位节点和一个tail节点标志尾节点

2.遍历两条有序链表，谁小就链接谁

3.最后还剩一条链表是没有遍历完成的，那么就让tail节点链接它

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {//1.新建哨兵位节点ListNode*　phead = new ListNode(-1);ListNode* tail = phead;//2.谁小就链接谁while(list1 && list2){if(list1->val > list2->val){tail->next = list2;tail = list2;list2 = list2->next;}else {tail->next = list1;tail = list1;list1 = list1->next;}}//3.判断谁还没有链接完if(list1) tail->next = list1;if(list2) tail->next = list2;return phead->next;}
};

---

反转链表

https://leetcode.cn/problems/reverse-linked-list/description/

prev：记录前一个节点 cur：当前遍历到的节点 next：保存cur的下一个节点

• 先保存下一个节点 然后更改cur的指向，指向前一个节点
• 然后迭代往后走

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* prev = nullptr;//记录前一个节点ListNode* cur = head;//记录当前节点ListNode* next = nullptr;//记录下一个节点while(cur){next = cur->next;//先保存下一个节点cur->next = prev;//更改当前节点指向//prev cur next 迭代往后走prev = cur;cur = next;}return prev;}
};

---

复制带随机指针的链表

https://leetcode.cn/problems/copy-list-with-random-pointer/

1.在原链表节点之后拷贝一个节点

2.处理拷贝节点的random指针

• 注意：拷贝节点的random指针指向的节点是其原链表节点的random指针指向的节点的下一个节点
• 坑点：有可能cur->random是空，也就是原来节点的random指针为空，那么当前拷贝节点的random指针也应该为空，否则cur->random->next 就会对空指针解引用！

3.分离两条链表

• 最好定义一个哨兵位节点和一个tail指针用于标记链接拷贝链表，
• cur CopyCur next三者的关系重新处理

class Solution {public:Node* copyRandomList(Node* head) {if(head == nullptr ) return nullptr;//1.在原节点后面copy一个节点Node* cur = head;while(cur){Node* copy = new Node(cur->val);//拷贝节点Node* next = cur->next;//cur copy next 链接cur->next = copy;copy->next = next;cur = next;//继续复制下一个节点}//2.处理拷贝节点的random指针cur = head;while(cur){Node*　curCopy = cur->next;//cur的拷贝节点curCopy->random = cur->random == nullptr?nullptr:cur->random->next;cur = curCopy->next;}//3.拆离拷贝链表cur = head;Node* pnewHead = new Node(-1);//哨兵位Node* tail = pnewHead;while(cur){//cur copyCur next  Node* copyCur = cur->next;Node* next = copyCur->next;copyCur->next = nullptr;//让拷贝节点独立存在tail->next = copyCur;tail = tail->next;//重新处理链接关系,向后走cur->next = next;cur = next;}return pnewHead->next;}
};

---

环形链表

https://leetcode.cn/problems/linked-list-cycle/description/

方法：使用快慢指针，二者从头开始走，一个一次走两步，一个一次走一步，当二者相遇的时候，说明有环

class Solution {
public:bool hasCycle(ListNode *head) {//链表为空//注意:一个节点也能成环！ 自己指向自己if(!head) return false;//快慢指针ListNode* fast = head;ListNode* slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;//二者相遇  注意:该条件不能放在上面！！！因为最初fast和slow都指向head,该条件应该放在下面if(slow == fast) return true;}return false;}
};

延申1：fast一次走两步,slow一次走一步,为什么一定能相遇？会不会在环里错过,永远遇不上

结论：slow一次走一步，fast一次走两步，如果存在环,slow和fast一定会在环内相遇

1.slow和fast，如果有环，一定是fast先进环，这时slow走了入环前距离的一半

2.随着slow进环，fast已经在环里面走了一段距离了（距离的多少跟环的大小有关）

• 假设slow进环的时候，slow和fast的距离为N，fast开始追赶slow

3.slow一次走一步，fast一次走两步，二者的距离变化为：N N- 1 N -2 … 0，当二者的距离变为0的时候，就是相遇了

延申2：fast一次走n步(n>2)，slow一次走一步，fast和slow能相遇吗

结论：fast一次走n步(n>2)，slow一次走一步，不一定会相遇

• 假设有环，fast一次走n步，slow一次走1步，fast和slow的距离不断减少n-1步

例子：假设fast一次走3步，如果slow进环之后，slow和fast的距离为N

如果N为偶数，那么二者之间的距离变化为：N N - 2 N - 4 … 2 0，此时二者相遇

如果N为计数，那么二者之间的距离变化为：N N - 2 N - 4 … 1 -1 ，二者距离变为-1，意味着fast超越了slow，此时fast和slow的距离为C -1 (假设C为环的大小)

• 如果C - 1 为偶数，那么下一轮fast可以追上slow，二者相遇
• 如果C - 1 为奇数，那么二者永远追不上

---

环形链表II

https://leetcode.cn/problems/linked-list-cycle-ii/description/

做法：

1.先看是否有环，快慢指针，fast一次走两步，slow一次走一步，如果存在环，fast和slow一定会相遇

2.假设相遇点为meetnode，一个指针从链表的头开始走，一个指针从相遇点开始走，二者一次走一步，当二者相遇的时候，该位置就是入环节点

class Solution {
public:ListNode *detectCycle(ListNode *head) {if(!head) return nullptr;//快慢指针ListNode* fast = head;ListNode* slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;//二者相遇  注意:该条件不能放在上面！！！因为最初fast和slow都指向head,该条件应该放在下面if(slow == fast) {//分别从相遇点和链表头开始走,一次走一步  此时相遇就是入环位置ListNode*　meet = slow;slow = head;while(slow != meet) {slow = slow->next;meet = meet->next;}return meet;}}return nullptr; //没有环}
};

---

相交链表

https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

方法1：将A链表的所有节点放到容器当中（要放地址，不能放值），然后遍历B链表，看能否在容器当中找到该元素，如果找到，那么该节点就是相交节点

class Solution {
public://方法1：用容器保存其中一个链表的节点,然后遍历另外一个链表进行比对ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {multiset<ListNode*> s;ListNode* cur = headA;while(cur) {s.insert(cur);cur = cur->next;}cur = headB;while(cur){cout << cur->val << endl;if(s.find(cur) != s.end()) return cur;cur = cur->next;}return nullptr;//不相交}
};

---

方法2：A中的每个结点和B分别比较(B和A比较也可以)，看二者的地址是否一致 - O(N*M)

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* curA = headA;ListNode* curB = headB;while(curA) //确定一个A节点{curB = headB;while(curB)//遍历整条B链表{if(curA == curB){return curA;}curB = curB ->next;}curA = curA->next;}return nullptr;}
};

方法3：

1.先统计两条链表的长度，假设二者长度差距为gap

2.长链表先往后走gap步，然后长短链表一起往后走，如果相遇，那么就是相交节点

class Solution {public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(!headA || !headB) return nullptr;//1.统计两条链表的长度int lenA = 0;int lenB = 0;ListNode* cur = headA;while(cur)  lenA++,cur = cur->next;cur = headB;