Day4 2023.12.3（昨天有事没写，按训练营时间，周天休息，我把第三天的补上） 代码随想录
1. 24两两交换链表中的节点 对于交换节点，不仅仅是值得交换，不然就很简单了，我们要交换的是节点，因此肯定需要定义多个临时节点控制交换，首先循环肯定得一个节点，并且继续采取头指针得方法，方便控制。其次，交换的两个节点需要临时节点存储。 大体思路如下 （注意，这里思路是我自己想得，与代码随想录有一些不同，不要混在一起看。。。） ：每次循环，循环节点指向两个需要交换节点得前一个节点，比如刚开始就指向头节点。当循环节点得next和next->next都为空时不满足交换条件（要么交换完了，要么节点数为奇数，最后剩一个节点不用交换。）然后循环中定义两个临时节点之江要交换的两个节点，在第一个循环中，也就是分别指向head->next和head->next->next;然后就是交换了，步骤很简单，但要注意顺序，第一步：循环节点next指向head->next->next，这就完成了第一步交换，后节点变到前面来了，第二步就是将原前节点->next连接到后续链表中，注意这里理解为什么要先连接到后续待处理链表上，而不是先将交换节点相连（因为交换节点相连，就是原后节点->next=原前节点，如果先进行这一步，那后续链表不就丢了吗？因为原后节点->next变了，那原始后面的一堆链表地址不就没了？），想象一下目前进行两步得结果，两个需要交换的链表，前面连接好了，后面连接好了，只剩下将两个需要连接得节点连在一起了，因此第三步就是原后节点->next=原前节点。循环就这三部，大功告成！
/**
* 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) {
ListNode*node = new ListNode(0);
node->next = head;
ListNode*n_node = node;
while(n_node->next!=nullptr && n_node->next->next!=nullptr){
ListNode * pre = n_node->next;
ListNode * next_node = n_node->next->next;
n_node->next = next_node;
pre->next = next_node->next;
next_node->next = pre;
n_node = pre;
}
return node->next;
}
};
2. 19删除链表的倒数第N个节点 这道题思路很巧妙，不接触得话感觉很难想到这种方法–双指针。很麻瓜的办法就是遍历算长度。。在遍历删除。。就不细说了。 本题思路：双指针，删除倒数第n个节点，也就是说删除节点跟最后一个节点的距离是n-1，那我们定义两个距离为n-1的指针，这样，一前一后，当前面指针指向最后一个节点时，那后面指针是不是就是我们要删除的节点呢？非常巧的方法，当然，这里说的距离可能有些不准确，但想表达的意思明白就行，具体的判断，我是手动推导两三种情况的逻辑下确定的，虽然挺费时间，但手动推导还是很有用的。 有一步是我没有注意的，后节点是我们要删除的节点，但好像没办法直接删除它，开始一直出错，最后才发现这个问题，因此有个技巧，控制好快慢指针的距离后，让前指针多走一步！。这样最后后者就是指向要删除节点的前一个指针，这样删除是不是就很方便了！
/**
* 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 *node = new ListNode(0);
node->next = head;
ListNode*low = node;
ListNode*fast = node;
while(n-->0){
fast = fast->next;
}
fast = fast->next;
while(fast!=nullptr){
low = low->next;
fast = fast->next;
}
low->next = low->next->next;
return node->next;
}
};
3. 07链表相交 这道题想了一会，感觉很直接的方法就是遍历长度，求差值，较长的链表前进该距离，让两个链表指针保持在同一相对位置，然后同时遍历就好，循环中一个if语句就行，挺麻瓜且直接的办法。。最后看代码随想录也是这种办法。也就不多想了。 代码逻辑很简单，但开始犯了个简单错误，遍历算长度后应该再次给两个索引节点赋给两个头节点，第一次没注意这个，因此后续较短链表遍历就出错了。
/**
* 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* a_node = headA;
ListNode* b_node = headB;
int a=0,b=0;
while(a_node!=NULL){
a_node=a_node->next;
a++;
}
while(b_node!=NULL){
b_node=b_node->next;
b++;
}
a_node = headA;
b_node = headB;
int temp =a>b ? a-b:b-a;
if(a>b){
while(temp--){
a_node = a_node->next;
}
}
else{
while(temp--){
b_node = b_node->next;
}
}
while(a_node!=NULL){
if(a_node==b_node){
return a_node;
}
a_node = a_node->next;
b_node = b_node->next;
}
return NULL;
}
};
4. 142环形链表Ⅱ 这道题以前做过，只记得判断有无环状是通过快慢指针判断的，即一个指针走两个，一个指针走一个，如果能遇到，则有环，不能遇到，则没有环。但对于怎么找到环入口的方法却忘z了。看了代码随想录后，觉得很神奇，确定有环后，即fast=slow，重新定义两个指针，一个指向相遇点，另一个指向链表第一个节点，两者同时移动，相遇点即是环状入口点。当然，这是结论，理论过程需要推导，可以见代码随想录详细解释
/**
* 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*low = head;
while(fast!=NULL&&fast->next!=NULL){
low = low->next;
fast = fast->next->next;
if(fast==low){
ListNode *a = fast;
ListNode*b = head;;
while(a!=b){
a = a->next;
b = b->next;
}
return a;
}
}
return NULL;
}
};
文章来源
发表评论