C++刷题 – 链表
文章目录
- C++刷题 -- 链表
- 1.删除链表的倒数第 N 个结点
- 2.链表相交
- 3.环形链表
1.删除链表的倒数第 N 个结点
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
快慢指针的应用
- fast指针先移动N步，slow依然指向head；
- 然后fast和slow同时移动，直到fast指向链表最后一个节点的next，也就是空，此时slow就指向了倒数第N个节点；
/**
* 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) {
if(head == nullptr || head->next == nullptr)
{
return nullptr;
}
ListNode* fast = head;
ListNode* slow = head;
ListNode* prev = nullptr;
//fast指针先移动N步，slow依然指向head
for(int i = 0; i < n; i++)
{
fast = fast->next;
}
//然后fast和slow同时移动，直到fast指向链表最后一个节点的next，也就是空，此时slow就指向了倒数第N个节点
while(fast)
{
fast = fast->next;
prev = slow;
slow = slow->next;
}
if(prev)
{
prev->next = slow->next;
delete(slow);
}
else // 如果prev为空，则删除的是头结点
{
prev = head;
head = head->next;
delete(prev);
}
return head;
}
};
2.链表相交
https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
- 两个链表相交之后的部分一定是相同的；
- 可以分别计算两个链表的长度，然后计算长度差
- 让两个链表从末尾对齐，如下图所示，指针curA和curB同时向后遍历，直到两者的指针地址相同；
/**
* 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 cntA = 0, cntB = 0;
ListNode* curA = headA;
ListNode* curB = headB;
//遍历得到AB的长度
while(curA)
{
cntA++;
curA = curA->next;
}
while(curB)
{
cntB++;
curB = curB->next;
}
//计算长度差，让长链表先走
int skip = abs(cntA - cntB);
ListNode* longerList = headA;
ListNode* shorterList = headB;
if(cntA < cntB)
{
swap(longerList, shorterList);
}
curA = longerList;
curB = shorterList;
while(skip--)
{
curA = curA->next;
}
//两个指针一起走
while(curA != curB)
{
curA = curA->next;
curB = curB->next;
}
return curA;
}
};
3.环形链表
https://leetcode.cn/problems/linked-list-cycle-ii/description/
判断链表是否有环
- 快慢指针：分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环
- fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇；
- 这是因为fast是走两步，slow是走一步，其实相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合
找到这个环的入口
- 假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。
-那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。 - 因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2
(x + y) * 2 = x + y + n (y + z) - 两边消掉一个（x+y）:
x + y = n (y + z) - 因为要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。
- 将x单独放在左面：
x = n (y + z) - y - 再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针
- 先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。
当 n为1的时候，公式就化解为x = z - 这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
- 也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。
让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。
- 那么 n如果大于1是什么情况呢，就是fast指针在环形转n圈之后才遇到 slow指针。
其实这种情况和n为1的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。
/**
* 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* fast = head;
ListNode* slow = head;
while(fast && fast->next) //如果没有环，fast或者fast->next就会为空
{
fast = fast->next->next; //快指针一次走两步
slow = slow->next; //慢指针一次走一步
//若有环，则fast和slow会在环内相遇
if(fast == slow)
{
//两个指针从相遇节点和头节点同时向后走，最终的相遇点就是环的入口
ListNode* index1 = head;
ListNode* index2 = fast;
while(index1 != index2)
{
index1 = index1->next;
index2 = index2->next;
}
return index2;
}
}
return nullptr;
}
};
