24. 两两交换链表中的节点
题目链接： 力扣
思路
我的一开始的失误点：定义三个指针移动元素，外加一个临时指针保存元素，导致后面循环的条件一直整不对，最终一直报空指针异常的错误
正确的思路：
首先：节点应该怎么交换(下图红色箭头代表需要交换的节点)，节点两两交换的时候，我们应该知道这两个节点之前的节点和之后的节点的，要不然节点就连不上了。比如，现在要交换1、2节点，我们要站在dummyhead的位置上进行交换（定义指针从虚拟头节点开始），而且要保存3节点，交换后为demmyhead-->2-->1-->3，这样才算完成一次交换，写交换节点过程的代码，按照交换后的顺序写就可以
dummy.next = 2
2.next = 1
1.next =3
其次：交换的终止条件在哪里，这是这个题目的一个难点，很容易会想不明白，cur是我们定义的节点，那就看一下指针在什么情况下就不在对节点进行交换了
从下图中我们可以看出（下图红色箭头代表cur），如果链表节点数为奇数，那么在cur.next.next == null 的时候，就不用再进行交换了。如果链表的节点数为偶数，那么再cur.next == null 的时候，就不在进行交换了
所以，能继续交换下去的条件是 cur.next != null && cur.next.next != null
cur是虚拟头节点，不可能为空，所以上面的判断条件是会判断链表中没有节点和链表中只有一个节点的情况
最后：为了交换节点，我们还需要定义相应的临时节点，如下图：
第一次交换：cur指向节点dummyhead，交换条件成立。进行交换
第二次交换：cur指向节点2，交换条件成立。进行交换
第三次交换：cur指向节点4，交换条件不成立，终止循环
两两交换链表中的节点
class Solution { public ListNode swapPairs(ListNode head) { // 创建虚拟头节点 ListNode dummy = new ListNode(0); dummy.next = head; // 指针指向头节点 ListNode cur = dummy; while (cur.next != null && cur.next.next != null) { ListNode temp1 = cur.next; ListNode temp2 = cur.next.next; ListNode temp3 = cur.next.next.next; cur.next = temp2; temp2.next = temp1; temp1.next = temp3; // 指针向前进行移动 cur = cur.next.next; } return dummy.next; } }
19. 删除链表的倒数第N个节点
题目链接：力扣
思路
这道题主要要解决两个问题：1、怎么找到倒数第n个节点 2、怎么删除对应的节点
怎么找到倒数第n个节点：我们可以定义两个指针，让第一个指针先走n步，第一个指针走到n节点的时候，开始同时移动两个节点。当先走的节点走到链表末尾null的时候。此时后走的节点就会在倒数第n个节点上，如下图:
怎么删除对应的节点：按照上图的方法，我们可以找到倒数第n个对应的节点，但是当slow指向这个节点的时候，没有办法对这个节点进行删除，因为删除这个节点，我们需要知道上一个节点，所以我们需要改变一下终止循环的条件，让fast指针移动到最后一个节点就可以，这样slow就指向3节点，可以对4节点进行删除操作，如下图
删除链表的倒数第N个节点
第一步：创建虚拟头节点，以便将头节点和其他节点统一化；创建双指针，便于对节点进行删除
第二步：首先移动fast指针
第三步：一起移动slow指针和fast指针
第四步：删除节点
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // 创建虚拟头节点 ListNode dummy = new ListNode(0); dummy.next = head; // 创建两个指针 ListNode slow = dummy; ListNode fast = dummy; // 首先移动fast指针 while ( n-- > 0) { fast = fast.next; } // 再一起移动fast指针和slow指针 while ( fast.next != null) { fast = fast.next; slow = slow.next; } // 进行删除 slow.next = slow.next.next; return dummy.next; } }
160. 链表相交
题目链接:力扣
思路
其实这个题目更像是模拟，只要想到要将两个链表的末尾对齐，这个题目就差不多了
然后再需要注意的问题，就是不一定就是A链表就更长，在进行下面找链表节点的过程中我们一定要知道哪个节点是长的，哪个节点是短的，为了同意，可以将curA指向更长的链表，有利于后面的处理
这个题目不需要虚拟头节点，定义了也是多余的，因为这里的头节点只有可能进行比较，不进行删除
链表相交
第一步：计算两个链表的长度
第二步：找出长度较长的链表
第三步：对齐链表（末尾对齐）
第四步：遍历找相交的节点
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode curA = headA; ListNode curB = headB; int sizeA = 0; int sizeB = 0; // 计算两个链表的长度 while (curA != null) { sizeA++; curA = curA.next; } while (curB != null) { sizeB++; curB = curB.next; } // 指针归位 curA = headA; curB = headB; // 让curA为最长链表的头，sizeA为其长度 if (sizeB > sizeA) { // 交换sizeA和sizeB int tmpSize = sizeA; sizeA = sizeB; sizeB = tmpSize; // 交换curA和curB ListNode tmpCur = curA; curA = curB; curB = tmpCur; } // 如果本身curA就是curB长，那就跳过上面的判断，直接来到这里 // 求链表的长度差 int len = sizeA - sizeB; // 先让curA进行移动，让curA和curB在同一个起点上（链表末尾对齐的情况下） while (len-- > 0) { curA = curA.next; } // 同时移动两个指针，遇到相同就返回节点 while (curA != null) { if (curA == curB) { return curA; } curA = curA.next; curB = curB.next; } return null; } }
142. 环形链表II
题目链接：力扣
思路
使用快慢指针的方式：
1、为什么使用快慢指针的方式？
假设这个链表是没有环的，是一条直线，那么快指针走得快，慢指针走得慢，这种情况下慢指针和快指针是永远无法相遇的，慢指针追不上快指针
除非这个链表是有环的，快指针走进链表的环里面的时候转圈了，慢指针进入环后这两个指针才有可能相遇
2、快慢指针分别走多块？
快指针每次走两个节点，慢指针每次走一个节点。如果两个指针进到环里面，那么快指针相对慢指针每次以一个节点的速度靠近慢指针
判断链表是否有环：
首先是快指针进入环，然后才是慢指针进入环，进入环之后，快指针相对慢指针每次以一个节点的速度靠近慢指针，快慢指针肯定会环里面相遇
找到环的入口：
x为头节点到环的入口处节点的位置的长度
y为从入口处节点的位置到相遇点的长度
z为相遇点到入口处节点的长度
假设fast和slow相遇了
那么此时：
slow指针走过的长度为： x + y
fast指针走过的长度为：x + n(y + z) + y
按照两个指针移动的速度，有等式成立：
2（x + y）= x + n (y + z) + y
x + y = n (y + z)
x = (n - 1) (y + z) + z
以上得到的等式非常重要，意味着 x = z , y + z 只是快指针在环中的转圈
注：快指针肯定在环里面至少走了一圈
慢指针肯定在环里面没走完一圈就被转上
为什么慢节点只在环里面走了一圈就被追上了，没有在环里面转圈圈？
将环形链表铺开来看，假设慢指针在环中走了一圈，以快指针的速度肯定走了两圈了，是肯定会有一个相遇点的，所以slow走过的距离为x+y，不会是x + k (y + z)
环形链表II
第一步：创建快慢指针
第二步：移动快慢指针。找出相遇点
第三步：定义两个指针，分别从相遇点和头节点出发
第四步：相遇处就是入口书处
public class Solution { public ListNode detectCycle(ListNode head) { // 创建快慢指针 ListNode fast = head; ListNode slow = head; // 判断fast不能为空。因为快指针是两步两步跳的，所以也需要判断fast.next不能为空 while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { // 这种情况是有环的，快慢指针相遇，记录相遇点 ListNode index1 = fast; // 给头节点来一个指针，跟相遇点指针一起走，相遇处就是入口处 ListNode index2 = head; while (index1 != index2) { index1 = index1.next; index2 = index2.next; } return index1; } } return null; } }
