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

题目：https://leetcode.cn/problems/swap-nodes-in-pairs/description/
讲解：https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html
复习可以先看视频讲解：（贴一张视频讲解的图）

思想

• 搞清while()循环的终止条件，链表长度为奇数、偶数都记得考虑
• 交换两个节点，需要定位到两个节点之前的一个节点的位置

解题

/*** 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 swapPairs(ListNode head) {//先设置一个虚拟头节点ListNode dummy=new ListNode(0,head);//让cur指向两个交换节点之前的节点ListNode cur=dummy;//当链表中元素个数为奇数时，cur.next.next==null为终止条件//当链表中元素个数为偶数时，cur.next==null为终止条件while(cur.next!=null&&cur.next.next!=null){//先暂存交换的第一个和两个需要交换的元素的后一个元素（即1，2交换时,暂存节点1和3）ListNode temp=cur.next;ListNode temp1=cur.next.next.next;cur.next=cur.next.next;cur.next.next=temp;cur.next.next.next=temp1;//偏移curcur=temp;	//等价于cur = cur.next.next;}return dummy.next;}
}//参考答案，上面是我写的，参考答案会比较清晰
// 将步骤 2,3 交换顺序，这样不用定义 temp 节点
public ListNode swapPairs(ListNode head) {ListNode dummy = new ListNode(0, head);ListNode cur = dummy;while (cur.next != null && cur.next.next != null) {ListNode node1 = cur.next;// 第 1 个节点ListNode node2 = cur.next.next;// 第 2 个节点cur.next = node2; // 步骤 1node1.next = node2.next;// 步骤 3node2.next = node1;// 步骤 2cur = cur.next.next;}return dummy.next;
}

总结

和思想一样喽，主要在上面那张讲解图；

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

题目：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
文章讲解：https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html

思想

• 用一个快指针fastIndex和一个慢指针lowIndex，让快指针先走n+1个位置，这样便可以保证两指针之间的间隔为n，然后同时移动两指针直至fastIndex到达链表尾后，lowIndex的下一个位置即为要删除的倒数第n个节点；

解题

/*** 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 dummy=new ListNode(0,head);ListNode fastIndex=dummy;ListNode slowIndex=dummy;//让fastIndex先走n+1个位置，这样fastIndex和slowIndex之间就间隔n个元素for(int i=0;i<=n;i++){fastIndex=fastIndex.next;}while(fastIndex!=null){fastIndex=fastIndex.next;slowIndex=slowIndex.next;}if(slowIndex.next.next==null){slowIndex.next=null;return dummy.next;}//slowIndex的下一个元素即为需要删除的元素slowIndex.next=slowIndex.next.next;return dummy.next;}}////这是参考答案，更好理解，上面我自己写的
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {//新建一个虚拟头节点指向headListNode dummyNode = new ListNode(0);dummyNode.next = head;//快慢指针指向虚拟头节点ListNode fastIndex = dummyNode;ListNode slowIndex = dummyNode;// 只要快慢指针相差 n 个结点即可for (int i = 0; i <= n; i++) {fastIndex = fastIndex.next;}while (fastIndex != null) {fastIndex = fastIndex.next;slowIndex = slowIndex.next;}// 此时 slowIndex 的位置就是待删除元素的前一个位置。// 具体情况可自己画一个链表长度为 3 的图来模拟代码来理解// 检查 slowIndex.next 是否为 null，以避免空指针异常if (slowIndex.next != null) {slowIndex.next = slowIndex.next.next;}return dummyNode.next;}
}

总结

记住思想的内容；

面试题 02.07. 链表相交

题目：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
文章讲解：https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html

思想

（1）方法一：

• 先计算出两条链表的长度，让链表A固定一直为长链表，计算两链表长度差值，让链表A先移动差值个单位，使A链表剩余长度和B链表相等，然后同时遍历两链表并比较对应节点是否相同；

（2）方法二：

解题

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//分别遍历两个链表拿到链表长度ListNode curA=headA;int sizeA=0;ListNode curB=headB;int sizeB=0;while(curA!=null){curA=curA.next;sizeA++;}while(curB!=null){curB=curB.next;sizeB++;}curA=headA;curB=headB;//让curA始终指向长链表，curB指向短链表if(sizeA<sizeB){//交换curA和BListNode temp=curA;curA=curB;curB=temp;//交换长度int temp1=sizeA;sizeA=sizeB;sizeB=temp1;}int gap=sizeA-sizeB;while(gap-->0){curA=curA.next;}while(curA!=null){if(curA==curB){return curA;}curA=curA.next;curB=curB.next;}return null;}
}////这是参考答案，更好理解，上面我自己写的
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode curA = headA;ListNode curB = headB;int lenA = 0, lenB = 0;while (curA != null) { // 求链表A的长度lenA++;curA = curA.next;}while (curB != null) { // 求链表B的长度lenB++;curB = curB.next;}curA = headA;curB = headB;// 让curA为最长链表的头，lenA为其长度if (lenB > lenA) {//1. swap (lenA, lenB);int tmpLen = lenA;lenA = lenB;lenB = tmpLen;//2. swap (curA, curB);ListNode tmpNode = curA;curA = curB;curB = tmpNode;}// 求长度差int gap = lenA - lenB;// 让curA和curB在同一起点上（末尾位置对齐）while (gap-- > 0) {curA = curA.next;}// 遍历curA 和 curB，遇到相同则直接返回while (curA != null) {if (curA == curB) {return curA;}curA = curA.next;curB = curB.next;}return null;}}