题目：24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
样例：
输入：head = [1,2,3,4] 输出：[2,1,4,3]输入：head = [1,2,3] 输出：[2,1,3]输入：head = [1] 输出：[1]
非递归实现
思路：1.先排除空节点和单个节点；2对于两个节点需要交换他们的顺序，类似数组中的交换值，所以需要一个临时变量cur，但是需要注意的是节点的数量不定，所以需要给dummy也增加一个res(类似waterer观察者，移动指针)，res 用来移动，跳到指定下一个需要交换位置的节点，然后重复交换节点的操作。
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 两个节点
ListNode dummy = null;
ListNode res = null;
ListNode cur = head;
while (cur != null) {
if (cur.next != null) {
// 临时节点
ListNode tmp = cur.next;
cur.next = cur.next.next;
tmp.next = cur;
cur = tmp;
if (dummy == null) {
dummy = tmp;
res = dummy;
} else {
// 节点往后移动
res.next.next = tmp;
res = res.next.next;
}
}
if (cur.next == null) {
break;
}
cur = cur.next.next;
}
return dummy;
}递归实现
递归：寻找数据的规律，在方法中处理这组数据，往复循环
官方题解
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
}题目：19. 删除链表的倒数第 N 个结点
样例：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]输入：head = [1], n = 1 输出：[]
遍历实现
思路：
1.去除空节点；
2.遍历节点获得节点长度；
3.判断：
1）如果节点长度减去待删除节点下标的值index == 0 ，说明删去的是第一个节点，直接返回head.next即可
2）寻找待删除节点（即index ）前一个节点，通过index-- == 1。然后定义一个临时节点，将节点的next 指向下一个节点即可。
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head == null){
return null;
}
int size = 0;
ListNode cur = head;
while(cur != null){
size++;
cur = cur.next;
}
int index = size - n;
if(index == 0){
return head.next;
}
ListNode res = head;
ListNode tmp = null;;
while(res != null){
if(index-- == 1){
tmp = res;
tmp.next = tmp.next.next;
}
res = res.next;
}
return head;
}双指针实现
思路：使用快慢指针，其中快指针先走 n 步， fast -slow = n ， 但是题目要求删去第 n 个节点，所以让fast 多走一步（需要考虑fast 已经走到链表尾部，这种情况只需头节点后移一个节点即可），在这种情况下， fast 指向 null 的时候 ， slow 指向 倒数 n+1 个节点，然后执行 slow.next = slow.next.next 即可删去第 n 个节点。
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
ListNode slow = head;
while(n-- >0){
fast = fast.next;
}
if(fast == null){
return head.next;
}
fast = fast.next;
while(fast != null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
}题目：142. 环形链表 II
样例：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
Map实现
思路：将对应节点存入Map, 遍历链表，如果回环，则返回该节点
public ListNode detectCycle(ListNode head) {
Map<ListNode, Integer> map = new HashMap<ListNode, Integer>();
ListNode cur = head;
int index = 0;
while(cur != null){
if(!map.containsKey(cur)){
map.put(cur, index);
}else{
return cur;
}
index++;
cur = cur.next;
}
return null;
}双指针实现（快慢指针）
官方题解思路：
fast 比 slow 多走一步
(1)如果不存在环，则fast == null 时 返回null
(2)如果存在环，则它们一定在环中相遇，但是此时不一定时环的入口节点。因此将fast 重新指向头节点，两个指针再次移动，相遇点既是环的入口点。
公式：
非环长 a 环长 b
fast,slow 步数 fastSteps , slowSteps
第一次相遇时 n 为 fast 比 slow 多走的圈数
fastSteps = 2 * slowStepsfastSteps = slowSteps + n * b
===>
fastSteps = 2 * n * b文章来源：https://www.toymoban.com/news/detail-853275.htmlslowSteps = n * b
假设需要找到环入口节点，需要走的步数为 k = a + n * b
由上推导公式易得，slow 只需要再走a 步 即可到环入口节点
在第一次fast , slow 相遇时，让fast 指向头节点，和 slow 一起移动，当fast == slow 即说明到达了入口节点处文章来源地址https://www.toymoban.com/news/detail-853275.html
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(true){
if(fast == null || fast.next == null) return null;
fast = fast.next.next;
slow = slow.next;
if(fast == slow) break;
}
fast = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return fast;
}到了这里，关于代码随想录第四天 两两交换链表中的节点的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
