1、LeetCode24 两两交换链表中的节点
题目链接:24、两两交换链表中的节点
要想清楚终止条件,cur每次指向要交换的两个节点的前一个节点,cur = cur->next->next;
若链表元素个数为偶数 , 则最后时刻 cur->next = NULL;
若链表元素个数为奇数,则最后时刻 cur->next->next = NULL;
最后要返回 dummyHead->next, 因为交换节点后 head 为 “2”,不是原来的 “1”。
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode * dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode * cur = dummyHead;
while(cur->next!=NULL && cur->next->next!=NULL)
{
ListNode * temp = cur->next;
ListNode * temp1 = cur->next->next->next;
cur->next = cur->next->next;
cur->next->next = temp;
cur->next->next->next = temp1;
cur = cur->next->next;
}
return dummyHead->next;
}
};
2、LeetCode19 删除链表的倒数第N个节点
题目链接:19、删除链表的倒数第N个节点
用快慢指针,快指针先向后移动N+1个节点,然后当快指针不为NULL时,快慢指针一起向后移动,快指针为NULL时,慢指针刚好移动到 倒数第N个节点的前一个节点。
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode * dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode * fast = dummyHead;
ListNode * slow = dummyHead;
n++;
while(n-- && fast!=NULL)
{
fast = fast->next;
}
while(fast!=NULL)
{
fast = fast->next;
slow = slow->next;
}
ListNode * temp = slow->next;
slow->next = slow->next->next;
delete temp;
return dummyHead->next;
}
};
3、LeetCode160 链表相交
题目链接:160 链表相交
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;
// 让curA为最长链表的头,lenA为其长度
if (lenB > lenA)
{
swap(lenA,lenB);
swap(cura,curb);
}
//求长度差
int gap = lenA - lenB;
while (gap--)
{
cura = cura->next;
}
while(cura)
{
if (cura == curb)
{
return cura;
}
cura = cura->next;
curb = curb->next;
}
return NULL;
}
};
4、LeetCode142 环形链表
题目链接:142、环形链表
找相遇节点,相遇节点和头结点同时出发,相遇时即为环形入口节点。(太厉害了,自己是想不出来。)文章来源:https://www.toymoban.com/news/detail-454670.html
文章来源地址https://www.toymoban.com/news/detail-454670.html
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode * fast = head;
ListNode * slow = head;
while (fast!=NULL && fast->next!=NULL)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
ListNode * index1 = head;
ListNode * index2 = fast;
while (index1 != index2)
{
index1 = index1->next;
index2 = index2->next;
}
return index1;
}
}
return NULL;
}
};
到了这里,关于代码随想录刷题第4天|LeetCode24、LeetCode19、LeetCode160、LeetCode142的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!