Leetcode24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）
//
class Solution{
public ListNode swapParis(ListNode head){
listNode dummyhead=new listNode(-1,head); //定义一个虚拟头结点 指向head
ListNode cur =dummyhead; //不直接用dummyhead 来操作
while(cur.next!=null&&cur.next.next!=null){ //必须是&& 因为只有 成对的两个节点才会进行交换
ListNode temp=cur.next.next.next; // 用来 保存 需要交换的两个节点之后的 节点
ListNode pred=cur.next; //保存 第一个要交换的节点；
cur.next=pred.next;
cur.next.next=pred;
pred.next=temp; //三步 交换 两个节点顺序
cur=cur.next.next //cur 直接向后遍历两个位置
}
}
}
//方法2 递归法 [解析链接](https://lyl0724.github.io/2020/01/25/1/ "解析链接")
class Solution{
public ListNode swapParis(ListNode head){
if(head==null||head.next==null){
return head;
}
ListNode pre=head.next;
head.next=swapParis(pre.next);
pre.next=head;
return pre;
}
}
leetcode 19删除链表倒数第N个节点
class Solution{
public ListNode removeNthFromEnd(ListNode head, int n) {
LinkNode dummyNode=new LinkNode(-1 ,head); //设置虚拟头结点
ListNode fast=dummyhead;
ListNode slow =dummyhead; //设置 快慢指针，解题关键：先让 快指针 向后遍历 n次 慢指针留在原
//地，此时 款满指针距离为 n-1，然后快慢指针一起向后遍历,
//直到快指针到最后一个节点 ，此时快慢指针 慢指针落在要删除的节点前一个位置。
for(int i=0;i<n;i++){
fast=fast.next;
}
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
slow.next=slow.next.next;
return dummyNode.next;
}
}
142. 环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
题目分为两个步骤 1：先判断是否有环 2找到环的入口
设置 一个 快慢指针 fast 速度为2， slow速度为1
如果有环， 那么 fast和slow一定会在环里面相遇
假设环的入口 为 a ， 入口到相遇的位置为b
slow 走到了b， 走了 a+b的路程
又因为fast是slow 速度的两倍 所以 fast 走了2*（a+b）
所以 slow 绕环继续走 a+b 又回到了b点，所以环剩下的长度 也等于 a
可以利用这个条件 让一个节点 从头开始遍历 ，另一个节点从相遇的地方开始遍历，速度相同，路程也相同，那么相遇的地方就是环的入口了。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fastNode=head;
ListNode slowNode=head;
boolean hasCycle=false;
while(fastNode!=null&&fastNode.next!=null && fastNode.next.next!=null){
fastNode=fastNode.next.next;
slowNode=slowNode.next;
if(fastNode==slowNode){
hasCycle=true;
break;
}
}
if(hasCycle){
ListNode cur = head;
while(cur!=slowNode){
cur=cur.next;
slowNode=slowNode.next;
}
return cur;
}else{
return null;
}
}
}
///面试题 02.07. 链表相交 难度不大 有点麻烦
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a=headA;
ListNode a1=headA;
ListNode b=headB;
ListNode b1=headB;
int lengthA=0,lengthB=0;
while(a!=null){
lengthA++;
a=a.next;
}
while(b!=null){
lengthB++;
b=b.next;
}
if(lengthB>lengthA){
int temp=lengthA;
lengthA=lengthB;
lengthB=temp;
ListNode tmepNode=a1;
a1=b1;
b1=tmepNode;
}
int lengthGap=lengthA-lengthB;
while(lengthGap-->0){
a1=a1.next;
}
while(a1!=null){
if(a1==b1){
return a1;
}
a1=a1.next;
b1=b1.next;
}
return null;
}
}