行业知识
代码随想录算法训练营第day4|24. 两两交换链表中的节点 、 19.删除链表的倒数第N个节点 、面试题 02.07. 链表相交 、 142.环形链表II
a.24. 两两交换链表中的节点
题���链接
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1,2,3,4]输出:[2,1,4,3]
示例 2:
输入:head = []输出:[]
示例 3:
输入:head = [1]输出:[1]
思路:
初始时,cur指向虚拟头结点,然后进行如下三步:
操作之后,链表如下:
/** * 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); dummyhead->next=head;//虚拟头节点指向实际头节点 ListNode* cur=dummyhead; while(cur->next!=nullptr&&cur->next->next!=nullptr){ //保存中将节点 ListNode* temp1=cur->next; ListNode* temp2=cur->next->next->next; //交换节点 cur->next=cur->next->next;//步骤1 cur->next->next=temp1;//步骤2 temp1->next=temp2;//步骤3 //cur移动两步 cur=cur->next->next; } return dummyhead->next; }}; b. 19.删除链表的倒数第N个节点
题目链接
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
示例 1:
输入:head = [1,2,3,4,5], n = 2输出:[1,2,3,5]
示例 2:
输入:head = [1], n = 1输出:[]
示例 3:
输入:head = [1,2], n = 1输出:[1]
思路:删除节点,只需令被删除节点前一个节点的next指针指向被删节点下一个节点即可。为了方便将头节点当普通节点处理,可以采用虚拟头节点的方法。那么如何找到被删节点呢?题目要求删除链表的倒数第 n 个结点,并且返回链表的头结点。
这道题是双指针的经典应用,如果要删除倒数第n个节点,让fast移动n步,然后让fast和slow同时移动,直到fast指向链表末尾。删掉slow所指向的节点就可以了。
当然,由于我们删除的是倒数第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* dummyHead= new ListNode(0); dummyHead->next=head; ListNode* fast=dummyHead; ListNode* slow=dummyHead; //快指针移动N+1步 while(n--&&fast->next!=nullptr){ fast=fast->next; } //快慢指针依次移动 while(fast->next!=nullptr){ fast=fast->next; slow=slow->next; } ListNode* temp =slow->next; slow->next=slow->next->next; delete temp; return dummyHead->next; }}; c.160.链表相交
题目链接
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。
图示两个链表在节点 c1 开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
示例 1:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3输出:Intersected at '8'解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
示例 2:
输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1输出:Intersected at '2'解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。
示例 3:
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2输出:null解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。这两个链表不相交,因此返回 null 。
思路:求两个链表交点节点的指针。 这里要注意,交点不是数值相等,而是指针相等。
首先两个链表长短不一,将尾部对齐后,交点肯定不在长链表“多出来得那一截里。因此可以将长链表移动到尾部对齐后的短链表头节点对应处开始比较,这里就要求出两个链表长度了。
注意链表A,B谁长谁端不一定,这里也得处理一下;
/** * 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) { int lenA=0; int lenB=0; ListNode* curA=headA; ListNode* curB=headB; while(curA!=nullptr){ lenA++; curA=curA->next; } while(curB!=nullptr){ lenB++; curB=curB->next; } curA=headA; curB=headB; //处理一下,保证链表A比链表B长 if(lenAnext; } //比较节点而非比较节点值 while(curB!=nullptr){ if(curA==curB)return curA; curA=curA->next; curB=curB->next; } return nullptr; }}; d.142.环形链表II
题目链接
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1:
输入:head = [3,2,0,-4], pos = 1输出:返回索引为 1 的链表节点解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0输出:返回索引为 0 的链表节点解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1输出:返回 null解释:链表中没有环。
思路:先判断是否有环,再找出环在哪。
判断是否有环,可以使用快慢指针法,分别定义 fast 和 slow 指针,从头结点出发,fast指针每次移动两个节点,slow指针每次移动一个节点,如果 这个链表有环,fast 和 slow指针在必定途中相遇。
此时从头结点出发一个指针,从相遇节点 也出发一个指针,这两个指针每次只走一个节点, 那么当这两个指针相遇的时候就是 环形入口的节点。
具体推理参考:代码随想录 (programmercarl.com)
/** * 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* slow = head; ListNode* fast = head; //寻找相交点 while(fast!=nullptr&&fast->next!=nullptr){ fast=fast->next->next;//快指针移动两步 slow=slow->next;//慢指针移动一步 //如果有交点,一个指针从交点出发,一个指针从头节点出发,依次移动 if(fast==slow){ ListNode* index1=fast; ListNode* index2=head; while(index1!=index2){ index1=index1->next; index2=index2->next; } return index1; } } return nullptr; }}; 参考链接:代码随想录 (programmercarl.com)
下一篇:生化5服务器在哪里进货?