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]
思路分析
方法一:逆向思维法
删除倒数第n个节点 ==> 删除正数N-n+1个节点.
图解:(以实例一为例)
方法一:快慢指针
先搞一个虚拟头结点,方便我们接下来的操作.
- 第一步slow和fast都指向虚拟头结点.
- 第二步fast向前移动n+1个节点
- slow和fast同时向前移动,直至fast为空,则slow对应的便是目标节点的前一个节点.
图解
参考代码
方法一:逆向思维法
//方法一:逆向思维法 删除倒数第n个节点 ==> 删除正数N-n+1个节点. ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *dummyHead = new ListNode(-1,head); ListNode *cur,*temp; cur = dummyHead->next; int N = 0,m;//总结点 while(cur) { N++; cur=cur->next; } //删除第n个节点 m = N-n; cur = dummyHead; while(m--){//指针指向第m个位置 cur=cur->next; } temp = cur->next;//保存删除节点 cur->next = cur->next->next;//进行删除 delete temp; // delete dummyHead; head = dummyHead->next; //最后的head一定要重新赋值哦,因为之前的head 可能已经挂了. delete dummyHead; return head; }
方法二:双指针法
//方法二:双指针法(快慢指针法) ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *dummyHead = new ListNode(-1,head); ListNode *slow = dummyHead,*fast = dummyHead,*temp; //fast先走n+1步 while(n>=0) { fast = fast->next; n--; } //slow和fast同时开始走,直到fast为NULL while(fast!=NULL) { slow = slow->next; fast = fast->next; } //进行删除 temp = slow->next; slow->next = slow->next->next; delete temp; head = dummyHead->next; delete dummyHead; return head; }
面试题 02.07. 链表相交
题目描述
给你两个单链表的头节点 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
解释：相交节点的值为 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 。
思路分析
题目的要求是求两个链表的交点,但是这里的交点是指针相等,不是节点里面的值相同.
看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点,如何求得交点呢.
我们可以求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：
此时我们就可以让CurA和CurB,从前往后遍历各自链表的节点,直到两者相等,此时对应的便是交点. 如果两个链表都遍历完还没有找到,则说明没有交点.
参考代码
#include<bits/stdc++.h> using namespace std; struct ListNode { int val; ListNode* next; ListNode() {} ListNode(int x):val(x),next(nullptr) { } ListNode(int x,ListNode* next):val(x),next(next) { } }; //方法:双指针 //先求出两条链表长度,然后最长两个指针指向最短的起始位置 ,同时向后移动.知道遇到公共结点 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *pointerA = headA,*pointerB = headB; int lenA = 0,lenB = 0,gap;//a:b代表两条链表的长度 while(pointerA) {//求LenA长度 lenA++; pointerA = pointerA->next; } while(pointerB) {//求LenB长度 lenB++; pointerB = pointerB->next; } 始终让A的长度比B大 if(lenA>lenB) { pointerA = headB; pointerB = headA; gap = lenA-lenB; }else{ pointerA = headA; pointerB = headB; gap = lenB-lenA; } while(gap--) {//B指针移动到和A指针相同的位置 pointerB = pointerB->next; } while(pointerA&&pointerB) {//A和B一起向前移动 if(pointerA==pointerB){//如果相同则直接进行返回 return pointerA; } pointerA = pointerA->next; pointerB = pointerB->next; } return NULL;//如果没有公共结点,则返回NULL; }
