文章目录
- 22. 两两交换链表中的节点
- 19. 删除链表的倒数第N个节点
- size-n方式删除
- 双指针方式（推荐）
- 面试题 02.07. 链表相交
- 142. 环形链表II
- 暴力解法
- 快慢指针（推荐）
22. 两两交换链表中的节点
leetcode链接：两两交换链表中的节点
文档讲解：两两交换链表中的节点
视频链接：代码随想录-两两交换链表中的节点
状态：先看的讲解视频，理解后就写出来了，估计不先看讲解很难写出来；
思路：
1、首先，两两交换相邻的两个节点，我们需要先创建一个虚拟头节点来进行操作（为了让操作更统一，如果不借助此，交换的情况还需要区分交换的节点是否包含头节点，代码会显的乱）；需要借助一个curNode指针来帮我们完成整个遍历操作，他需要指向两个交换节点的前一个节点；另外我们还会借助两个指针temp和temp1（如下图）来帮助我们完成两两交换；
2、交换的思路我们分成三步：a. 首先将curNode.next指向curNode.next.next，但是我们做这一步前，需要先借助temp指针来保存节点1，因为如果我们不保存，当我们做完curNode.next指向curNode.next.next之后，无法对节点1进行操作；b.然后将curNode.next.next = temp,如下图中的步骤2，这时候temp就起到了作用，但是这时候又有新的问题，当我们调整了原节点2的next后，又无法操作节点3了，所以这就是我们事先用temp1保存对节点3的操作；c.最后一步就是将temp.next指向temp1；经过以上三步就实现了节点1和节点2的交换，当处理完节点1和节点2之后，curNode应该调整为curNode.next.next，即指向如下图的节点3的位置上；
3、最后还得考虑什么时候遍历结束的问题，当链表的长度是偶数的时候，curNode.nextnull时遍历就结束了，如果长度是奇数，那么当curNode.next.nextnull的时候遍历结束；所以我们的遍历条件应该为while(curNode.next!=null&&curNode.next.next!=null)。
代码：
class Solution {
public ListNode swapPairs(ListNode head) {
//创建一个虚拟头节点
ListNode dummyHead = new ListNode();
dummyHead.next = head;
//创建一个指针，该指针指向需要交换的两个元素的前一个元素；
ListNode curNode = dummyHead;
//链表遍历结束表达式,如果链表长度是偶数，两两进行交换，那么当curNode.next = null时循环结束
//如果链表长度是奇数，那么当curNode.next.next=null时循环结束
while (curNode.next != null && curNode.next.next != null) {
ListNode temp = curNode.next; //用于临时存储需要交换的第一个元素
ListNode temp1 = curNode.next.next.next; //用于临时存储交换元素的第二个元素的next；防止调整第二个交换元素next后，找不到原next；
//交换操作,最好画图帮助理解；
curNode.next = curNode.next.next;
curNode.next.next = temp;
temp.next = temp1;
curNode = curNode.next.next;
}
return dummyHead.next;
}
}
19. 删除链表的倒数第N个节点
leetcode链接：删除链表的倒数第N个节点
文档讲解： 删除链表的倒数第N个节点
视频链接：代码随想录-删除链表的倒数第N个节点
状态：自己写出来了，明天看看视频讲解，看看和视频里的思路是不是一样的；
size-n方式删除
思路：
1、这种方式其实是我第一时间想到的，思路也很简单，先获取到链表的长度，然后找到要删除节点的前一个节点实现删除；
代码：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//先找到链表的长度
int size = 0;
ListNode curNode = head;
while (curNode != null) {
size++;
curNode = curNode.next;
}
if (size == 0) {
return head;
}
//删除单链表的节点需要找到要删除节点的前一个节点,但是如果要删除的是头节点，则不会有前一个节点，为了保证规则统一，创建一个虚拟头结点；
int preNodeIndex = size - n;
if (preNodeIndex < 0) {
return head;
}
ListNode dummyHead = new ListNode();
dummyHead.next = head;
curNode = dummyHead;
for (int i = 0; i < preNodeIndex; i++) {
curNode = curNode.next;
}
curNode.next = curNode.next.next;
return dummyHead.next;
}
}
双指针方式（推荐）
思路：
1、看了视频讲解之后，觉得此方法很妙，其实按照视频里的方法逆向思考了下，要删除倒数第N个节点，说明要删除节点和最后一个节点的距离是N-1，那么最后一个节点离要删除节点的前一个节点的距离就是N；
2、那么此时，我们想象有个长度N的窗口，窗口从最左边往最右边移动，当窗口的最右边指向链表的最后一个元素的时候，窗口的左边就只想要删除的节点的前一个节点；
代码：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head==null) {
return head;
}
ListNode dummyHead = new ListNode();
dummyHead.next = head;
//定义快慢节点
ListNode fastNode = dummyHead;
ListNode slowNode = dummyHead;
//从dummyHead开始出发，让快节点先移动n步；
while (n>0&&fastNode.next!=null) {
fastNode = fastNode.next;
n--;
}
//快指针移动n步之后，快慢指针此时同时移动
while (fastNode.next!=null) {
fastNode = fastNode.next;
slowNode = slowNode.next;
}
slowNode.next = slowNode.next.next;
return dummyHead.next;
}
}
面试题 02.07. 链表相交
leetcode链接：链表相交
文档讲解：链表相交
视频链接：无
状态：看了文档讲解后写出来了，一开始老去考虑比较值去了，应该站在两个链表相交的角度来看待的，这个题还挺有意思的；明天对比一下写的代码和文档讲解的代码是否相似；
思路：
1、这一题的思路看了解析之后挺简单的，先获取到两个链表的长度；然后分别定义两个指针tempA和tempB指向链表的头节点；将两个指针按照长度对齐；对齐之后，两个指针同时移动，判断tempA==tempB,如果两个指针指向的是同一个节点，则说明有相交节点，直接返回，如果没有找到，则返回null；
代码：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//此题的关键在于，要想清楚，相交节点的判断是要比较两个节点的地址是否相同，而不是值
int aListSize = 0;
int bListSize = 0;
//先找到链表的长度
ListNode curNode = headA;
while (curNode!= null) {
aListSize++;
curNode=curNode.next;
}
curNode = headB;
while (curNode!= null) {
bListSize++;
curNode=curNode.next;
}
//定义两个指针对齐向后查找
ListNode tempB = headB;
ListNode tempA = headA;
//指针对齐操作，如果a链表比b链表长
if (aListSize > bListSize) {
int sub = aListSize - bListSize;
//因为链表a比b长，所以tempA需要先对齐；
for (int i = 0; i < sub; i++) {
tempA = tempA.next;
}
} else {
int sub = bListSize - aListSize;
//因为链表b比a长，所以tempB需要先对齐；
for (int i = 0; i < sub; i++) {
tempB = tempB.next;
}
}
//开始查找；
while (tempA != null && tempB != null) {
//判断tempA和tempB是否相同；
if (tempA == tempB) {
return tempA;
}
tempA = tempA.next;
tempB = tempB.next;
}
//没找到返回null
return null;
}
}
142. 环形链表II
leetcode链接：环形链表II
文档讲解：环形链表II
视频链接：代码随想录-环形链表
状态：自己暴力解法写出来了，强烈推荐看视频解析，这道题好有意思；
暴力解法
思路：
1、自己一刷的时候想出来的，思路很简单，如果链表中存在环形链表，那么我借助一个Set集合（无序，不可重复）和一个遍历指针，每遍历一个节点就放入set集合中，如果有一个节点放入时发现已经存在了，说明有一个节点重复了，这个节点就是环链的入口；属于瞎猫碰到死耗子做出来了；
代码：
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
Set<ListNode> nodeSet = new HashSet<ListNode>();
ListNode curNode = head;
while (curNode!=null) {
if (nodeSet.contains(curNode)) {
return curNode;
} else {
nodeSet.add(curNode);
curNode = curNode.next;
}
}
return null;
}
}
快慢指针（推荐）
思路：
1、我们定义分别定义好快慢指针fast，slow，同时他们分别按照每次移动两位和移动一位的方式向前遍历；如果链表存在环链，那么fast和slow肯定会在环链的某个节点相遇，那么如果把head到环链入口的距离设置为x，环链入口到相遇点的距离设置为y，相遇点到环链入口的距离设置为z；此时需要印证出两个推论，如果有环链，那么slow肯定在没走完一圈的情况下会被fast追上（至于为什么，有数学论证，可以看视频或者自己实验）；
那么相遇时我们可以得到：slow(走过的距离) = x+y； fast(走过的距离) = x+y+n(圈数)*(z+y);
因为相遇两个指针时间是一样的，fast的速度是slow速度的两倍，那么可以得到：
2(x+y) = x+y+n(z+y) => x+y = n*(z+y) => x = n*(z+y) - y => x = (n-1)(z+y) + z => x=z**
（此处可以想象把整个距离铺开，仔细体会为什么x=z)；
2、经过1的分析，我们代码的思路就是，先定义快慢指针，然后找到相遇点，找到相遇点temp1之后，再定义一个指针temp2=head，让temp1和相遇点2同时遍历，直到temp1==temp2时返回；
代码：
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return head;
}
ListNode fast = head;
ListNode slow = head;
while (fast.next!=null && fast.next.next!=null) {
fast = fast.next.next; //速度2
slow = slow.next; //速度1
if (fast == slow) { //说明存在环形链表,此时fast和slow都指向相遇点
ListNode temp1 = head;
ListNode temp2 = fast;
while (temp1 != temp2) {
temp1 = temp1.next;
temp2 = temp2.next;
}
return temp1;
}
}
return null;
}
}
