代码随想录算法训练营day4 | 题目24、题目19、面试题 02.07、题目142
题目一描述
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
提示：
- 链表中节点的数目在范围
[0, 100]内 0 <= Node.val <= 100
解题思路
画图，模拟，可以大胆的，多设置几个辅助指针。
代码实现
方法一：
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode slow = dummyHead;
ListNode fast = slow.next;
while(fast!= null&& fast.next!=null){
ListNode temp = fast.next;
slow.next = temp;
fast.next = temp.next;
temp.next = fast;
slow = fast;
fast = slow.next;
}
return dummyHead.next;
}
}
方法二（递归）：
class Solution {
public ListNode swapPairs(ListNode head) {
// 最后进入函数的子链表头结点，是空或者单个，返回
if(head== null || head.next==null)
return head;
// 针对通用的操作，定义两个指针
ListNode one = head;
ListNode two = one.next;
// 交换位置，链接后面返回的头结点
one.next = swapPairs(two.next);
two.next = one;
// 返回新链表的头结点
return two;
}
}
技巧总结
处理递归，核心就是千万不要想子问题的过程。要想子问题的结果，思路就清晰了
递归应该关心的主要有三点：
1，返回值
2，调用单元做了什么
3，终止条件
在本题中：
1，返回值：交换完成的子链表
2，调用单元：设需要交换的两个点为 head 和 next，head 连接后面交换完成的子链表，next 连接 head，完成交换
3，终止条件：head 为空指针或者 next 为空指针，也就是当前无节点或者只有一个节点，无法进行交换
题目二描述
给你一个链表，删除链表的倒数第 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 <= 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 dummyNode = new ListNode(-1, head);
ListNode slow = dummyNode;
ListNode fast = dummyNode;
for (int i = 0; i < n + 1; i++) {
fast = fast.next;
}
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummyNode.next;
}
}
技巧总结
注意dummyHead的初始化，不要直接指向dummyHead不是直接指向head的。
注意fast和slow指针应该直接指向节点，而不是自我初始化之后通过next连接，不然的话若是删除头结点，由于slow是新的节点，所做的操作只是把slow这个新节点指向了第二个数字，而不是通过slow操作dummy来指向第二个数字。
题目三描述
提示
给你两个单链表的头节点 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 * 10^41 <= Node.val <= 10^50 <= skipA <= m0 <= skipB <= n- 如果
listA和listB没有交点，intersectVal为0 - 如果
listA和listB有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？
解题思路
这道题也可以用，快慢指针先走差值的方法来做，计算两条链表的长度，然后取差值让长的先走，由于若是相交最后会同步，所以可以找到交点。
也可以让这两条走完自己的再去走另一条的，走到最后若是还没有相交点就是没交点，退出条件是指针相等，不会死循环因为各自走完自己的和对方的之后会指向null，也是一种相等。
代码实现
方法一：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode ListA = headA;
ListNode ListB = headB;
int lengthA = 0;
int lengthB = 0;
while (ListA != null) {
ListA = ListA.next;
lengthA++;
}
while (ListB != null) {
ListB = ListB.next;
lengthB++;
}
ListA = headA;
ListB = headB;
int gap = Math.abs(lengthA - lengthB);
if (lengthA > lengthB) {
for (int i = 0; i < gap; i++) {
ListA = ListA.next;
}
} else {
for (int i = 0; i < gap; i++) {
ListB = ListB.next;
}
}
while (ListA != null) {
if (ListA == ListB) {
return ListA;
}
ListA = ListA.next;
ListB = ListB.next;
}
return null;
}
}
方法二：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode l1 = headA;
ListNode l2 = headB;
while(l1 != l2){
l1 = l1 == null ? headB : l1.next;
l2 = l2 == null ? headA : l2.next;
}
return l1;
}
}
技巧总结
快指针先走然后快慢指针同步走，很重要的方法。
题目四描述
给定一个链表的头节点 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, 10^4]内 -10^5 <= Node.val <= 10^5-
pos的值为-1或者链表中的一个有效索引
进阶：你是否可以使用 O(1) 空间解决此题？
解题思路
也是快慢指针，需要推导一个数学公式出来。
slow指针走了x+y，fast指针走了x+n(y+z) +y，由于步速差异，2(x+y) = x+n(y+z)+y
x + y= n(y+z)
这里n大于等于1，代表的是一种事实：slow指针走过的距离是快指针在环内走的总步数，这个事实没什么意义，我们只是取合适的n=1来简化情况
假设n=1，带入得到 x = z
所以判断相遇后，再从头结点走x步，slow走z步，两个指针同时走，走完的落点就是入口节点。
也用到了先差异，后同步走的思路
代码实现
方法一：
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode dummyHead = new ListNode(0, head);
ListNode fast = dummyHead;
ListNode slow = dummyHead;
ListNode index = dummyHead;
int i = 0;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
while (index != slow) {
index = index.next;
slow = slow.next;
}
return index;
}
}
return null;
}
}
方法二（使用了额外的空间。就当学习一下Set的用法了）：
public class Solution {
public ListNode detectCycle(ListNode head) {
Set<ListNode> map = new HashSet<>();
ListNode index = head;
while(index != null){
if(map.contains(index)){
return index;
}
else{
map.add(index);
}
index = index.next;
}
return null;
}
}
技巧总结
注意多指针的初始化，最好都初始化到同一个位置。
Set的初始化，判断是否有值，添加值的方法。
