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;
//偏移cur
cur=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; // 步骤 1
node1.next = node2.next;// 步骤 3
node2.next = node1;// 步骤 2
cur = 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) {
//新建一个虚拟头节点指向head
ListNode 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和B
ListNode 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;
}
}