题目：
面试题 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 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 这两个链表不相交，因此返回 null 。
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int sizeA = 0;int sizeB = 0;ListNode curA = headA;ListNode curB = headB;while(curA != null){curA = curA.next;sizeA++;}while(curB != null){curB = curB.next;sizeB++;}curA = headA;curB = headB;if(sizeB > sizeA){int tmpSize = sizeA;sizeA = sizeB;sizeB = tmpSize;ListNode tmpNode = curA;curA = curB;curB = tmpNode;}int gap = sizeA - sizeB;while(gap-- > 0){curA = curA.next;}while(curA != null){if(curA == curB){return curA;}curA = curA.next;curB = curB.next;}return null;}
}寻找两条链表的对齐方法，发现可以从尾巴那里开始对齐
19、删除链表的倒数第N个结点
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]提示：
- 链表中结点的数目为
sz1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(-1,head);ListNode slow = dummy;ListNode fast = dummy;int size = 0;while(fast != null){fast = fast.next;size++;}int len = size - n - 1;fast = dummy;while(len-- > 0){slow = slow.next;}fast = slow.next;slow.next = fast.next;return dummy.next;}
}本题的思想是快慢指针和链表相交的结合，fast先去探路，然后计算出路程，然后让slow慢fast一步，再运用虚拟头结点方便删除head，不是很难。
24. 两两交换链表中的节点
已解答
中等
相关标签
相关企业
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]示例 2：
输入：head = [] 输出：[]示例 3：
输入：head = [1] 输出：[1]提示：
- 链表中节点的数目在范围
[0, 100]内0 <= Node.val <= 100
题解：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode swapPairs(ListNode head) {ListNode dummy = new ListNode(-1,head);ListNode cur = dummy;ListNode temp;ListNode firstNode;ListNode secondNode;while(cur.next != null && cur.next.next != null){temp = cur.next.next.next;firstNode = cur.next;secondNode = cur.next.next;cur.next = secondNode;secondNode.next = firstNode;firstNode.next = temp;cur = firstNode; }return dummy.next;}
}这一题主要是需要定义的节点很多，然后交换起来很复杂，容易出错，思路还好并不费解，但是想要做对实在不是一件简单的事
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 解释：链表中没有环。提示：
- 链表中节点的数目范围在范围
[0, 104]内-105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = 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;}
}本题是一个数学题，比较复杂，详细请看代码随想录
![[云原生] k8s之存储卷](https://img-blog.csdnimg.cn/direct/896b564be187492e890acb718b6fa03d.png)
