今日刷题4道:24. 两两交换链表中的节点19.删除链表的倒数第N个节点面试题 02.07. 链表相交142.环形链表II。
● 24. 两两交换链表中的节点
题目链接/文章讲解/视频讲解: https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html
碎碎念:本题是对相邻的两个结点进行交换,注意是交换结点,不是值。需要设虚拟头结点,注意保存多个临时变量即可。
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
dummyHead->next = head; // 将虚拟头结点指向head,这样方面后面做删除操作
ListNode* cur = dummyHead;
while(cur->next != nullptr && cur->next->next != nullptr) {
ListNode* tmp = cur->next; // 记录临时节点
ListNode* tmp1 = cur->next->next->next; // 记录临时节点
cur->next = cur->next->next; // 步骤一
cur->next->next = tmp; // 步骤二
cur->next->next->next = tmp1; // 步骤三
cur = cur->next->next; // cur移动两位,准备下一轮交换
}
return dummyHead->next;
}
};
● 19.删除链表的倒数第N个节点
碎碎念:这个题比较熟,写的很快,思路和卡哥的一样,写法稍有不同,就是快慢指针确定倒数第n个元素的位置,如果要删除的话,就是它前一个元素的位置,拿捏了。
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyNode = new ListNode(0); dummyNode -> next = head; ListNode* cur = dummyNode; ListNode* slow = dummyNode; int count = 0; while(cur -> next){ cur = cur -> next; if(count < n) count++; else{ slow = slow -> next; } } cur = slow -> next; slow -> next = cur -> next; delete cur; return dummyNode -> next; } };● 面试题 02.07. 链表相交
碎碎念:不看题解毫无思路,看了以后发现好简单啊,重点要想到,交点之后的长度是一样的,所以找两个链表的长度差,然后一 一比较就行了。
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode* curA = headA; ListNode* curB =headB; int lenA = 0; int lenB = 0; while(curA){ lenA++; curA = curA -> next; } while(curB){ lenB++; curB = curB -> next; } curA = headA; curB = headB; int gap; gap = lenA > lenB ? lenA - lenB : lenB - lenA; if(lenA > lenB && gap != 0) { while(gap--){ curA = curA -> next; } } else{ while(gap--){ curB = curB -> next; } } while(curA){ if(curA == curB) return curA; else{ curA = curA -> next; curB = curB -> next; } } return NULL; } };● 142.环形链表II
题目链接/文章讲解/视频讲解:https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html
碎碎念:需要画图看一下,做好距离等式才能做出来。
class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode* fast = head; ListNode* slow = head; ListNode* index1; ListNode* index2; while(fast != NULL && fast -> next != NULL){ fast = fast -> next -> next; slow = slow -> next; if(fast == slow){ index1 = head; index2 = fast; while(index1 != index2){ index1 = index1 -> next; index2 = index2 -> next; } return index1; } } return NULL; } }; 标签:ListNode,cur,训练营,curA,随想录,next,链表,curB,第四天 From: https://www.cnblogs.com/zzw0612/p/17016905.html