④ 链表

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

题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/

注意点：

遍历链表的时候什么时候截止（避免空指针异常或无限死循环的问题）？

• 节点数量为偶数或链表为空时，cur.next == null 为 true 时即可终止循环

• 节点数量为奇数时，cur.next.next == null 为true 时即可终止循环

• while(cur.next != null &&  cur.next.next != null){}
  

交换的代码具体怎么写？

解题思路：

定义一个虚拟头节点dummyhead，操作的指针cur（cur = dummyhead）一定要指向要反转的两个节点的前一个节点，如图所示

根据反转后的结果来看，cur指向2，2指向1，1指向3

具体操作如下：

最后，返回链表

代码：

class Solution {public ListNode swapPairs(ListNode head) {ListNode dummyhead = new ListNode(-1);  // 定义一个虚拟头节点dummyhead.next =  head;ListNode cur = dummyhead;ListNode temp1;ListNode temp2;while(cur.next != null && cur.next.next != null){temp1 = cur.next;   // 临时节点，保存两个节点之中的第一个节点temp2 = cur.next.next.next;    // 临时节点，保存下一轮交换中的两个节点中的第一个节点cur.next = cur.next.next;   cur.next.next = temp1;temp1.next = temp2;cur = cur.next.next;}return dummyhead.next;}
}

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

题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

注意点：

操作指针要指向被删除节点的前一个节点

如何找到倒数的第n个节点？设置快慢指针。

解题思路：

定义一个虚拟头节点（省去对头节点的特殊判断），设置一个快指针一个慢指针，让快指针先移动n+1步，然后快慢指针再同时移动，直到快指针指向空节点，这样慢指针就指向了被删除的节点的前一个节点。

代码：

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummyhead = new ListNode(-1);dummyhead.next = head;ListNode slow = dummyhead;  // 慢指针ListNode fast = dummyhead;  // 快指针// 快指针向前移动n+1位for(int i=0;i<=n;i++){fast = fast.next;}// 同时移动快慢指针while(fast != null){fast = fast.next;slow = slow.next;}// 删除节点slow.next = slow.next.next;return dummyhead.next;}
}

142.环形链表II

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/

注意点：

判断链表是否有环？设置快慢指针，有环的情况下，快慢指针一定会相遇。

如何找到环的入口？

解题思路：

定义快慢指针，快指针从起点出发以每次走两个节点的速度前进，慢指针从起点出发以每次走一个节点的速度前进；如果两个指针相遇，说明这个链表有环。

再定义两个节点，一个从头结点出发，一个从快慢指针相遇的节点出发，当这两个指针相遇时，此节点便是环的入口节点。

代码：

public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head;  // 快指针ListNode slow = head;  // 慢指针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;}
}