您现在的位置是:首页 >其他 >C++ | LeetCode 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II网站首页其他
C++ | LeetCode 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II
简介C++ | LeetCode 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II
24. 两两交换链表中的节点
- 为啥最开始需要将current节点指向虚拟头结点,是因为想要交换节点1和节点2的值,虚拟头结点、节点1和节点2的指向都需要发生改变。
- 需要注意的是,当改变一个节点的next值后,原先的链接就没了。所以当需要改变一个节点的next值后,需要先将该节点指向的节点先用临时变量存储下来。
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* virtualHead = new ListNode(0);
virtualHead->next = head;
ListNode* current = new ListNode(0);
current = virtualHead;
while(current->next != NULL && current->next->next != NULL) {
ListNode* tmp1 = current->next;
ListNode* tmp2 = current->next->next->next;
current->next = current->next->next;
current->next->next = tmp1;
current->next->next->next = tmp2;
current = current->next->next;
}
return virtualHead->next;
}
};
19.删除链表的倒数第N个节点
- 暴力解法:先计算链表的长度,然后转换成正着数 第(总数 - N)个节点。
- 快慢指针法:让快节点先走 n 步, 然后快慢节点一块走,直到快节点走到末尾,那么慢节点即为所需要删除的节点。
- 因为要删除某个节点,需要获取它的上一个节点,所以需要让慢节点少走一步,即等价于快节点多走一步。
暴力解法
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
// 暴力解法
ListNode* virtualHead = new ListNode(0);
virtualHead->next = head;
ListNode* current = virtualHead;
int count = 0;
while(current->next != NULL) {
current = current->next;
count++;
}
current = virtualHead;
while((count - n) != 0) {
current = current->next;
count--;
}
ListNode* tmp = current->next;
current->next = current->next->next;
delete tmp;
return virtualHead->next;
}
};
快慢指针法
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
// 快慢指针法
// 让快节点先走 n 步, 然后快慢节点一块走,
// 直到快节点走到末尾,那么慢节点即为所需要删除的节点
ListNode* virtualHead = new ListNode(0);
virtualHead->next = head;
ListNode* fast = virtualHead;
ListNode* slow = virtualHead;
// 因为要删除某个节点,需要获取它的上一个节点,所以需要让慢节点少走一步,
// 即等价于快节点多走一步
n++;
// 在这里 fast != NULL 或者 fast->next != NULL 判断是否到达末尾的标志,
// 两者都行,一个指向NULL,一个指向尾节点, 但是无论选择那个,都要保持一致,
// 可以画个图梳理下,对于fast->next != NULL 就不需要n++了,
// 因为两者同步移动的时候 较之第一个条件,会整体少走一步。
while (n-- != 0 && fast != NULL) {
fast = fast->next;
}
while (fast != NULL) {
fast = fast->next;
slow = slow->next;
}
ListNode* tmp = slow->next;
slow->next = slow->next->next;
delete tmp;
return virtualHead->next;
}
};
面试题 02.07. 链表相交
- 若两个链表相交,则从相交位置他们的后面的长度一定相等,所以需要先将两者的长度对齐,两个链表相当于是右对齐,即让长的链表先走,直到和短列表长度相等,然后在逐个节点去判断。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* currentA = headA;
ListNode* currentB = headB;
int lengthA = 0;
int lengthB = 0;
while (currentA != NULL) {
currentA = currentA->next;
lengthA++;
}
while (currentB != NULL) {
currentB = currentB->next;
lengthB++;
}
currentA = headA;
currentB = headB;
int delta;
if (lengthA > lengthB) {
delta = lengthA - lengthB;
while (delta-- != 0) {
currentA = currentA->next;
}
} else if (lengthB > lengthA) {
delta = lengthB - lengthA;
while (delta-- != 0) {
currentB = currentB->next;
}
} else;
ListNode* interVal;
while(currentA != NULL) {
if (currentA == currentB) {
interVal = currentA;
return interVal;
}
else {
interVal = NULL;
}
currentA = currentA->next;
currentB = currentB->next;
}
return interVal;
}
};
142.环形链表II
- 暴力解法:将遍历的节点每次移动一个,就需要跟前面除自己的所有节点进行比对,是否有相等的,有则为环。简单粗暴但是效率太低。
- 快慢指针法:非常巧妙的运用了数学的知识,通过类似于速度路程关系,可以推出两者在圈内相遇后,从相遇点到入环处和从起点到入环处的距离是一样的,基于此等式,即可得出。
暴力解法
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
// 暴力解法
ListNode* currentA = head;
ListNode* currentB = head;
int count = 0;
while(currentB != NULL) {
currentB = currentB->next;
count++;
int tmpCount = count - 1;
// B每次移动一个,就需要跟前面除自己的所有节点进行比对,是否有相等的,有则为环。
currentA = head;
while (tmpCount-- != 0 && currentA != currentB) {
currentA = currentA->next;
}
if (tmpCount > 0) {
return currentA;
}
}
return NULL;
}
};
快慢指针法
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 = head;
ListNode* index2 = fast;
while (index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}
return index1;
}
}
return NULL;
}
};
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。