代码随想录算法训练营第4天| 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交 、142.环形链表II

JAVA语言编写

24. 两两交换链表中的节点

谷歌、亚马逊、字节、奥多比、百度

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

教程：https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

视频：https://www.bilibili.com/video/BV1YT411g7br

方法一：双指针法

思路：

操作之后的链表：

复杂度分析：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

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 dumyhead = new ListNode(-1); // 设置一个虚拟头结点dumyhead.next = head; // 将虚拟头结点指向head，这样方面后面做删除操作ListNode cur = dumyhead;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; // cur移动，准备下一轮交换}return dumyhead.next;}
}

19. 删除链表的倒数第 N 个结点

字节跳动、亚马逊、Facebook

给你一个链表，删除链表的倒数第 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]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

**进阶：**你能尝试使用一趟扫描实现吗？

教程：https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html

视频：https://www.bilibili.com/video/BV1vW4y1U7Gf

方法一：自己写的

思路：很简单的方法，首先写一个循环遍历head，获得当前val的个数size。根据倒数第n个数、与size及正着数的索引的关系：flag=size-n+1，删除结点。对于特殊情况，head为null，则返回空。若删除是头结点，也就是n=size的时候，直接返回head.next。

复杂度分析：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {
if (head==null) return null;int size=0;ListNode cur = head;ListNode temp=head;ListNode pre = new ListNode(0,temp);while(cur!=null){cur = cur.next;size++;//计算当前ListNode的个数}if(n==size) return head.next;//如果是删第一个的话，就返回head.nextint flag=0;//记录索引位置while(temp!=null){//temp是遍历的if(flag==size-n){//size-n是正数的索引前一个pre.next=temp.next;//删除操作}flag++;temp=temp.next;pre=pre.next;}return head;}
}

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 。

提示：

• listA 中节点数目为 m
• listB 中节点数目为 n
• 0 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

**进阶：**你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

教程：https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html

方法一：

思路：求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。否则循环退出返回空指针。

复杂度分析：

• 时间复杂度：$O(nA+nB)$,nA是链表A的长度,nB是链表B的长度
• 空间复杂度：$O(1)$

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode curA = headA;ListNode curB = headB;int lenA = 0, lenB = 0;while (curA != null) { // 求链表A的长度lenA++;curA = curA.next;}while (curB != null) { // 求链表B的长度lenB++;curB = curB.next;}curA = headA;curB = headB;// 让curA为最长链表的头，lenA为其长度if (lenB > lenA) {//1. swap (lenA, lenB);int tmpLen = lenA;lenA = lenB;lenB = tmpLen;//2. swap (curA, curB);ListNode tmpNode = curA;curA = curB;curB = tmpNode;}// 求长度差int gap = lenA - lenB;// 让curA和curB在同一起点上（末尾位置对齐）while (gap-- > 0) {curA = curA.next;}// 遍历curA 和 curB，遇到相同则直接返回while (curA != null) {if (curA == curB) {return curA;}curA = curA.next;curB = curB.next;}return null;}}

142. 环形链表 II

字节跳动、谷歌 Google、Facebook

给定一个链表的头节点 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 <= 105
• pos 的值为 -1 或者链表中的一个有效索引

**进阶：**你是否可以使用 O(1) 空间解决此题？

教程：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

视频：https://www.bilibili.com/video/BV1if4y1d7ob/

方法一：

思路：可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。

复杂度分析：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

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 = fast;ListNode index2 = head;// 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口while (index1 != index2) {index1 = index1.next;index2 = index2.next;}return index1;}}return null;}
}