php网站好吗,红旗渠建设集团网站,wordpress未找到页面,怎样申请自己企业的网站目录
一、24. 两两交换链表中的节点
二、19. 删除链表的倒数第 N 个结点
三、面试题 02.07. 链表相交 四、142. 环形链表 II 一、24. 两两交换链表中的节点 题目链接#xff1a;力扣
文章讲解#xff1a;代码随想录
视频讲解#xff1a; 帮你把链表细节学清楚#xff… 目录
一、24. 两两交换链表中的节点
二、19. 删除链表的倒数第 N 个结点
三、面试题 02.07. 链表相交 四、142. 环形链表 II 一、24. 两两交换链表中的节点 题目链接力扣
文章讲解代码随想录
视频讲解 帮你把链表细节学清楚 | LeetCode24. 两两交换链表中的节点_哔哩哔哩_bilibili
题目给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。
示例 1 输入head [1,2,3,4]
输出[2,1,4,3]
代码
/*** 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* dummyhead new ListNode(0, head);head dummyhead;while(head-next head-next-next){ListNode* front head-next;ListNode* rear head-next-next; front-next rear-next;rear-next front;head-next rear;head front;}head dummyhead-next;delete dummyhead;return head;//7:58}
};
时间复杂度: O(n) 空间复杂度: O(1)
⏲7:58
总结图中局部线的更改只有三条故函数中关于next语句的修改为三条。
二、19. 删除链表的倒数第 N 个结点
题目链接力扣
文章讲解代码随想录
视频讲解链表遍历学清楚 | LeetCode19.删除链表倒数第N个节点
题目给你一个链表删除链表的倒数第 n个结点并且返回链表的头结点。代码
/*** 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-next;ListNode* slow dummyhead;while(n--)fast fast-next;while(fast){fast fast-next;slow slow-next;}ListNode *des slow-next;slow-next slow-next-next;delete des;head dummyhead-next;delete dummyhead;return head;//5:31}
};
时间复杂度: O(n) 空间复杂度: O(1)
⏲5:31
总结1、要求倒数第n让fast指针先走n步即可 2、删除第n个结点要求前一个结点慢走一步即可。
三、面试题 02.07. 链表相交
题目链接力扣
文章讲解代码随想录
视频讲解
题目
给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回 null 。
图示两个链表在节点 c1 开始相交 题目数据 保证 整个链式结构中不存在环。
注意函数返回结果后链表必须 保持其原始结构 。
代码
/*** 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) {if (!headA || !headB) return NULL;ListNode* newA headA,*newB headB;while(newA ! newB){newA newA NULL ? headB : newA-next;newB newB NULL ? headA : newB-next;}return newA;}//11:06
};
时间复杂度: O(nm) 空间复杂度: O(1)
⏲11:06
假设Sa mt Sb nt
突破点SaSb m n 2t 则必在同时在最后交点处相遇。
总结1、链表的相交、循环问题在条件不多找不到突破点时可考虑使用数学方法从路径长度入手。 四、142. 环形链表 II
题目链接力扣
文章讲解代码随想录
视频讲解链表遍历学清楚 | LeetCode19.删除链表倒数第N个节点
题目给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改 链表。代码
/*** 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* slow head;do{if(!fast || !fast-next) return NULL;fast fast-next-next;slow slow-next;}while(fast ! slow);slow head;while(fast ! slow){fast fast-next;slow slow-next;}return slow;}
};
时间复杂度: O(n) 空间复杂度: O(1)
⏲31:37
思路 问题为什么第一次相遇必为b而非n(bc)b. 总结1.找相遇结点。两倍速的快慢指针。2.找环交点。起始位置和相遇位置同时出发相遇位置。
