[数据结构与算法]代码随想录算法训练营第四天|24. 两两交换链表中的节点 19.删除链表的倒数第N个节点 面试题 02.07. 链表相交 142.环形链表II

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

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

看到题目第一想法

引入虚拟头指针，临时指针指向虚拟头节点，一两个节点为单位通过此节点对后续两个节点进行指针方向的改变，同时为了防止丢失节点地址，再引入两个临时指针保存第1个和第二个节点信息。由于一两个节点为单位，其操作具有可重复性，可以使用递归方法。

//虚拟节点
/**
 * 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 dummyhead=new ListNode(-1,head);
        ListNode cur=dummyhead;
        while(cur.next!=null&&cur.next.next!=null){// cur.next在cur.next.next前否则空指针异常
        ListNode temp2=cur.next.next;//2
        ListNode temp1=cur.next;//1号位
        cur.next.next=cur.next.next.next;//1,2  -》1，3
        cur.next=temp2;//2跑1前
        cur.next.next=temp1;//1,2互换完毕
        cur=cur.next.next;
        }
        return dummyhead.next;

    }
}

//递归
/**
 * 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) {
        
        return swap(head);

    }
    public ListNode swap(ListNode head){
        
        ListNode dummyhead=new ListNode (-1 , head);
        ListNode cur=dummyhead;
      
        if(cur.next==null||cur.next.next==null){
            return cur.next;}
        ListNode temp2=cur.next.next;//2
        ListNode temp1=cur.next;//1号位
        cur.next.next=cur.next.next.next;//1,2  -》1，3
        cur.next=temp2;//2跑1前
        cur.next.next=temp1;//1,2互换完毕
        cur=cur.next.next;          
        cur.next=swap(cur);//cur之后两个节点为单位返回头节点、、、、、//应该放入参与交换的第一个点而不是前一个cur

        return dummyhead.next;}
    }

递归的代码运行后报错：Error - Found cycle in the ListNode。链表最后一个值的next一定要指向null，不然会报如下错误。检查发现是cur.next=swap(cur);出错。
应该放入参与交换的第一个点而不是前一个已经参与过倒位的cur。

更正之后

//改正
/**
 * 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 dummyhead=new ListNode (-1 , head);
        ListNode cur=dummyhead;
      
        if(cur.next==null||cur.next.next==null){
            
            return dummyhead.next;}
        ListNode temp2=cur.next.next;//2
        ListNode temp1=cur.next;//1号位
        cur.next.next=cur.next.next.next;
        cur.next=temp2;
        cur.next.next=temp1;
        cur=cur.next.next;
        cur.next=swapPairs(cur.next);//应该放入参与交换的第一个点而不是前一个cur
        return dummyhead.next;}
    }

    //临时指针指向要操作的两个节点的前一个节点

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？

示例 1：

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 示例 2：
输入：head = [1], n = 1 输出：[] 示例 3：
输入：head = [1,2], n = 1 输出：[1]

看到题目第一想法

首先应该定位倒数第n节点的位置，首先因为单链表是单向的不能从头走到尾再倒着计算，所以考虑用双指针，其具体实现一时没有头绪，在学习过后了解到采用快慢指针，快指针提前走n步，满指针再和快指针同步走，这样就保证两支针之间有n+1个数据，当快指针走到链尾（不是null），而慢指针为倒数第n+1个节点，可以通过此对滴=第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 dummyHead= new ListNode(-1,head);
        //快慢指针 快指针走n步 慢和快同时走直到快到结尾 即 快的下一个为空
        ListNode fast=dummyHead;
        ListNode slow=dummyHead;
        while(n!=0){
            fast=fast.next;
            n--;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
    return dummyHead.next;}

面试题 02.07. 链表相交

同：160.链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：

示例 2：

示例 3：

看到题目第一想法

此题开始错误地认为是节点中数值val相等为相交，实际不然。学习后发现，此题就是求两个链表交点节点的指针。 而交点不是数值相等，而是指针相等。
根据题目发现，相交的链表其链末端都是对齐的，因此首先分别计算出链表长度以及长度差，分别设置两个临时指针指向各自的头节点，让较长的临时指针先进行长度差个单位，后两个临时指针同时移动，直到找到相等的节点返回其节点。

/**
 * 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;
        ListNode curb=headB;
        int lengtha=0;
        int lengthb=0;
        while(cura!=null){
            lengtha++;
            cura=cura.next;
        }
        while(curb!=null){
            lengthb++;
            curb=curb.next;            
        }        
        ListNode curlong;
        ListNode curshort;
        int gap;
        if(lengtha>lengthb){
            curlong=headA;
            curshort=headB;
            gap=lengtha-lengthb;
        }else{curlong=headB;
            curshort=headA;
            gap=lengthb-lengtha;}
        while (gap!=0){
            curlong=curlong.next;
            gap--;}    
        while(curlong!=null){
            if(curlong==curshort){
               return curlong;  
            }else{curlong=curlong.next;
            curshort=curshort.next;}
        }return null;
    }
}

142.环形链表II

题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。

看到题目第一想法

此题较难，其步骤可以分为找环与找节点。
找环可以通过设置快慢节点，让慢节点去追击快节点，如若能追上则为有环。
而找相遇节点则未找到合适方法学习过后发现，需通过画图分析，建立数学关系解决此问题。
假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：

那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。
因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：
(x + y) * 2 = x + y + n (y + z)
两边消掉一个（x+y）: x + y = n (y + z)
要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。
所以要求x ，将x单独放在左面：x = n (y + z) - y ,
再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。
先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。
当 n为1的时候，公式就化解为 x = z，
这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。
让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。


n大于1和n为1的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。

//伪代码
//快指针 慢指针相遇验证是否有环
fast=head
slow=head
while(fast!=null&&fast.next!=null){//保证可以移两次
    fast=fast.next.next
    slow=slow.next
    if (slow=fast){
        index1=slow//相遇点
        index2=head
        while (index1!=index2){
            index1=index1.next
            index2=index2.next
        }return index1
    }
return null}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
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(slow==fast){
                ListNode index1=slow;
                ListNode index2=head;
                while(index1!=index2){
                    index1=index1.next;
                    index2=index2.next;
                }return index1;
            }
        }
    return null;}
}