【算法训练营day4】LeetCode24. 两两交换链表中的结点 LeetCode19. 删除链表的倒数第N个结点 LeetCode面试题 02.07. 链表相交 LeetCode142. 环形链表II
LeetCode24. 两两交换链表中的节点
题目链接：24. 两两交换链表中的节点
初次尝试
比较暴力的解法，利用三个指针，进行类似反转链表里面的反转next指针指向的操作，然后三个指针整体向后移动到下一组节点，暴力但是ac。
/**
* 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* swapPairs(ListNode* head) {
if (head == NULL || head -> next == NULL) return head;
ListNode* pre = head;
ListNode* cur = head -> next;
ListNode* temp = cur -> next;
head = head -> next;
while (true) {
cur -> next = pre;
pre -> next = temp;
if (temp != NULL && temp -> next != NULL) {
cur = temp -> next;
pre -> next = cur;
pre = temp;
temp = cur -> next;
}
else break;
}
return head;
}
};
看完代码随想录后的想法
思路差不多，忘记用虚拟头结点了，重新用虚拟头结点写了一下，ac。
/**
* 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* swapPairs(ListNode* head) {
if (head == NULL || head -> next == NULL) return head;
ListNode* dummyHead = new ListNode(0, head);
ListNode* cur = dummyHead;
while (cur -> next != NULL && cur -> next -> next != NULL) {
ListNode* temp1 = cur -> next;
ListNode* temp2 = cur -> next -> next;
cur -> next = temp2;
temp1 -> next = temp2 -> next;
temp2 -> next = temp1;
cur = cur -> next -> next;
}
return dummyHead -> next;
}
};
LeetCode19. 删除链表的倒数第N个结点
题目链接：19. 删除链表的倒数第N个结点
初次尝试
暴力解法，先遍历链表得出链表的长度，然后计算出倒数第n个结点的索引，然后删除，ac。
/**
* 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) {
ListNode* newHead = new ListNode(0, head);
ListNode* p = head;
int listSize = 0;
while (p != NULL) {
p = p -> next;
listSize++;
}
p = newHead;
ListNode* temp;
int delIndex = listSize - n;
while (delIndex > 0) {
p = p -> next;
delIndex--;
}
temp = p -> next;
p -> next = temp -> next;
delete temp;
return newHead -> next;
}
};
看完代码随想录后的想法
题解利用了快慢指针，快指针先移动n个结点，然后快慢指针同时移动，在移动过程中保持n距离不变，这样快指针到达链表尾部的时候，慢指针就正好位于要删除的结点，十分巧妙的思路，重新写一遍ac。
/**
* 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) {
ListNode* dummyHead = new ListNode(0, head);
ListNode* fast = dummyHead;
ListNode* slow = dummyHead;
for (; n > 0; n--) {
fast = fast -> next;
}
while (fast -> next != NULL) {
fast = fast -> next;
slow = slow -> next;
}
ListNode* temp = slow -> next;
slow -> next = temp -> next;
delete temp;
return dummyHead -> next;
}
};
LeetCode面试题 02.07. 链表相交
题目链接：面试题 02.07. 链表相交
初次尝试
没有想到解法，思路卡在了单链表不能回溯上面。
看完代码随想录后的想法
题解考虑到了两个链表的长度差，感觉和今天的第二题有异曲同工之妙，虽然单链表不能回溯，但是如果能提前知道需要回溯的长度，在第二题中就是倒数第n个，在本题中就是两个链表长度的差，这就是这类题中核心的“不变量”，通过使用保持这个距离同时移动的快慢指针，就可以从单链表不能回溯的思维定势中走出来。
/**
* 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) {
ListNode* pA = headA;
ListNode* pB = headB;
int aSize = 0, bSize = 0;
while (pA != NULL) {
aSize++;
pA = pA -> next;
}
while (pB != NULL) {
bSize++;
pB = pB -> next;
}
int offset = aSize - bSize;
pA = headA;
pB = headB;
if (offset >= 0) {
for (; offset != 0; offset--) {
pA = pA -> next;
}
}
else {
for (; offset != 0; offset++) {
pB = pB -> next;
}
}
while (pA != NULL) {
if (pA == pB) return pA;
pA = pA -> next;
pB = pB -> next;
}
return NULL;
}
};
LeetCode142. 环形链表II
题目链接：142. 环形链表II
初次尝试
没有想到解法，两年前见过用快慢指针解环链表问题的解法，解本题的时候也一直想怎么用来着？最后还是没有想起来具体是怎么用的。
看完代码随想录后的想法
刚看到需要数学计算的提示，就开始想自己先算一算，一开始以为是可以通过数学计算直接解出入环结点的索引，所以一直致力于解出具体的数字，后来发现解不出来就放弃了，完整看了视频题解，解法真的很巧妙，并没有解出什么具体的数字，而是通过理解等式本身的意义，得出了获得入环结点索引的方法，虽然这个解法不具有大规模的应用能力，但是很锻炼思维能力和计算能力。
/**
* 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) {
if (head == NULL || head -> next == NULL) return NULL;
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;
}
};
