[数据结构与算法]day4两两交换链表中的节点&删除链表的倒数第N个节点&环形链表II

今天做完链表的力扣题，感觉空指针异常应该不会再发生了；

1.力扣24题

这个题没什么比较难的算法，主要是更好的理解算法的next域，不要指来指去就蒙了

解题思路：

1. 定义一个虚拟头节点，用来统一操作链表，要养成使用虚拟头节点的习惯，会很方便。
2. 准备好后，定义一个cur节点用来遍历链表，循环结束条件是，cur.next!=null&&cur.next.next!=null，因为可能是奇数或者偶数个节点
3. 定义temp1和temp2节点用来存放1和3节点，方便后期的操作
4. 进行核心操作，cur.next = cur.next.next;连接cur和2节点
5. 此时cur的下个节点改变了，cur.next = temp1;让2节点和1节点连接，temp1.next=temp2.next；此时1和3节点都连接上了，完成交换操作。

代码如下：

    public ListNode swapPairs(ListNode head) {
        ListNode dummyhead = new ListNode(-1);
        dummyhead.next=head;
        ListNode cur = dummyhead;
        while(cur.next!=null&&cur.next.next!=null){
            ListNode temp1 = cur.next;
            ListNode temp2 = cur.next.next.next;

            cur.next = cur.next.next;
            cur.next.next = temp1;
            temp1.next = temp2;
            cur = cur.next.next;
        }
        return dummyhead.next;
    }

2.力扣19

本题需要用双指针，方便找到倒数第n个节点。

解题思路：

1. 定义一个虚拟头节点，指向head，完成准备操作
2. ?首先定义一个slow指针和fast指针，初始化都指向dummy节点，方便操作
3. 根据输入的n讲fast指针向后移动n个，slow指针不动
4. 让slow和fast都向后移动，直至fast指针指向最后一个元素，此时slow指针指向待删除元素的前一个位置
5. 进行删除操作，cur.next=cur.next.next;

代码如下：

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyhead = new ListNode(-1);
        dummyhead.next = head;
        ListNode slow=dummyhead;
        ListNode fast = dummyhead;
        for(int i=0;i<n;i++){
            fast = fast.next;
        }
        while(fast.next!=null){
            slow=slow.next;
            fast=fast.next;
        }
        slow.next = slow.next.next;
        return dummyhead.next;
    }

3.力扣142

本题有两个关键点，首先判断是否有环，其次求得入口的位置，思路比较难理解

解题步骤：

1. 首先利用快慢指针的相遇判断是否有环，slow指针每次走一个位置，而fast指针一次走两个位置，若有环则快指针总会追上慢指针。
2. 再判断有环的时候进行求入口节点操作，看下图进行讲解
3. 假设有环的时候，再某一点相遇，此时slow指针肯定没有走到一圈，而fast指针就追上了slow指针（可以自己模拟一下，讲圈化为直线）
4. 慢指针走了x+y距离，而快指针走了x+y+n*(z+y)，又因为节点相遇，且快指针的速度是慢指针的两倍速度，所以列出等式，2(x+y)=x+y+n*(z+y)，化简得x=(n-1)*(z+y)+z;当n=1时x=z，若n>1时得情况和n=1得时候一样，无非就是多走了几圈。
5. 进行计数操作，定义两个index1和index2节点，每次走一个节点直至相遇。

?

?代码如下：

    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(fast==slow){
                ListNode index1= fast;
                ListNode index2 = head;
                while(index1!=index2){
                    index1=index1.next;
                    index2= index2.next;
                }
                return index1;
            }
        }
         return null;
    }