学习内容
力扣算法：
24、两两交换链表中的节点
19、删除链表的倒数n个节点
07、链表相交
142、环形链表||
具体内容
24、两两交换链表中的节点
解题
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode listnode = new ListNode(-1,head);
ListNode pre = listnode;
//判断链表长度为单数还是偶数
while(pre.next != null && pre.next.next != null){
ListNode cur = pre.next;
ListNode cur1 = pre.next.next.next;
pre.next = pre.next.next;
pre.next.next = cur;
cur.next = cur1;
cur = cur.next.next;
}
return listnode.next;
}
}
代码中需要注意的地方
1、 while循环体的判断语句为何这样写
pre.next != null 判断链表个数为偶数， pre.next.next != null判断链表个数为奇数
2、在翻转指针时要多画图理解
cur虚拟头节点一定是指向要交换的两个节点的前一个节点
3、为什么while循环体是用&& 而不是||
结合图像判断，pre.next != null表示链表长度是单数，pre.next.next != null代表链表长度是双数，可结合上图来看
19、删除链表的倒数n个节点
解题
快慢指针
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//设立虚拟头节点
ListNode listnode = new ListNode(-1,head);
//快指针
ListNode fast = listnode;
//慢指针
ListNode slow = listnode;
//n取值要n+1 即n=0时依然循环 才能使slow到达要删除节点的前一个位置
while(n-- >= 0{
fast = fast.next;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return listnode.next;
}
}
代码中需要注意的地方
1、为什么求倒数第n个节点时，快指针走n+1步之后，slow紧跟后面直到快指针等于null，慢指针指向的便是我们所求的值？
双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
07、链表相交
解题
public class Solution {
//此题关键是要两个链表都从同一个位置开始遍历 因此一定要从短的链表开始往后遍历啊
//因此要求其长度
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0;
int lenB = 0;
//求A链表长度
while(curA != null){
lenA++;
curA = curA.next;
}
//求B链表长度
while(curB != null){
lenB++;
curB = curB.next;
}
//curA和curB初始化
curA = headA;
curB = headB;
//统一让lenA最长
if(lenB > lenA){
int temp = lenA;
lenA = lenB;
lenB = temp;
ListNode list = curA;
curA = curB;
curB = list;
}
//求长度差
int pre = lenA - lenB;
while(pre-- > 0){
curA = curA.next;
}
while(curA != null){
if(curA == curB){
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
}
解答代码存在的疑问
1、解题步骤
求两条长度不同链表相交的相同元素，由于长度不同，因此为了统一规则，可以先找出各自的链表长度，求长度差n，而较长链表在n个元素之前都不会与短链表相交，因此先让长链表遍历到n的位置，这样长短链表属于同一起点，便可一直往下走
142、环形链表||
解题
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;
//再从head出发 获取相遇的位置
while (index1 != index2) {
index1 = index1.next;
index2 = index2.next;
}
return index2; // 返回环的入口
}
}
}
解答代码存在的疑问
1、当求出了快慢指针的相遇位置时，为什么还要再用while循环求？
求出了快慢指针的相遇位置，只知道了fast在哪，还要求入口