代码随想录算法训练营第四天

LeetCode 24力扣​  ​​​​​

两两交换链表节点，采用原地交换，使用tmp节点进行交换前临时节点存储即可（三个一组）

package algor.trainingcamp;

import algor.junior_algor.list.ListNode;

/**
 * @author lizhe
 * @version 1.0
 * @description: 两两交换链表中的节点
 *
 * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
 * @date 2023/4/8 13:32
 */
public class LeetCode24 {
    /**
     * 先将原节点全部保存下来 然后进行赋值即可，以三个节点为一组
     */
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;

        ListNode cur = dummyHead;

        while(cur.next != null && cur.next.next != null){
            /**
             * 将 dummy -> 1 ->2 变成了 dummy -> 2 -> 1
             */
            ListNode temp1 = cur.next;
            ListNode temp2 = cur.next.next;
            ListNode temp3 = cur.next.next.next;


            cur.next = temp2;
            cur.next.next = temp1;
            cur.next.next.next = temp3;
            cur = cur.next.next;
        }

        return dummyHead.next;
    }
}

LeetCode19力扣

删除倒数第n个节点，先找到待删除节点的前一个，进行操作即可

package algor.trainingcamp;

import algor.junior_algor.list.ListNode;

/**
 * @author lizhe
 * @version 1.0
 * @description: 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * @date 2023/4/8 13:52
 */

/**
 * 如何找到倒数第n个节点的前一个位置，进行删除
 * 快慢指针从dummy开始，首先快指针向后移动n位，然后快慢一起移动，慢指针就到了待删除节点的前一个位置
 */
public class LeetCode19 {
    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;
    }
}

面试02.07 力扣

找出两个单链表的相交起始节点，相当于将一个节点的尾链接上另外一个节点的头部，然后进行遍历，如果有重合点，一定相交

package algor.trainingcamp;

import algor.junior_algor.list.ListNode;

/**
 * @author lizhe
 * @version 1.0
 * @description: https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
 * @date 2023/4/8 14:02
 *
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 */

/**
 * 思路: 假设a链表长度为a b链表长度为b，ab链表的公共部分长度为c
 *
 * 遍历a链表之后再开始遍历b链表，到达尾部时候共走了 a + b - c 步数
 * 遍历b链表之后再开始遍历a链表, 到达尾部时候共走了 b + a - c 步数
 *
 * 如果两个链表相交，一定有重合点 此时指向了公共交点
 * 如果两个链表不相交 则返回空
 */
public class LeetCode0207 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;

        /**
         * 刻意多往后遍历了一次，为了返回null
         */
        while(headA != headB){
            curA = curA != null ? curA.next : curB;
            curB = curB != null ? curB.next : curA;
        }

        return curA;
    }
}

LeetCode142 力扣

判断链表的成环点，具体的公式推导 在注释中，之前看过这道题，理解的第一次相遇后使用同样步长一个从相遇点走，一个从头走，距离一样（a == c）其实是错误的，a和c是有一定关系的(a = (n - 1)(c + b) + c ) c+b的整数倍刚好是一个环的长度。因此才最终会到成环点

package algor.trainingcamp;

import algor.junior_algor.list.ListNode;

/**
 * @author lizhe
 * @version 1.0
 * @description: https://leetcode.cn/problems/linked-list-cycle-ii/
 * @date 2023/4/8 14:29
 *
 * 判断链表是否有环，及环
 *
 * 假设 从链表的头 到 链表成环点距离为a，链表成环点到相遇点距离为b 相遇点到链表成环点距离为c
 *
 * 当相遇时
 * 则 慢指针走的路程为  a + b
 * 快指针为 a + b + c + b + c + b... a + b + n(c + b)[n >= 1]
 * 如若快指针是慢指针速度的两倍 a + b + n(c + b) = 2(a + b) => 可以化简为 a = (n - 1)(c + b) + c
 *
 * ！！！！
 * （n - 1）（c+b）已经是整个环的距离了，假设一个节点从相遇点出发，一个节点从原点出发，按照相同的速度，最终依旧会在成环点碰面，
 * 可能是一个点走了 a到达了成环点，另外一个点走了 (n - 1)(c + b) + c，最终也是会到达成环点
 */
public class LeetCode142 {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        //fast != null 考虑节点不成环的情况
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;

            if(fast == slow){
                slow = head;
                while(fast != slow){
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }

        return null;
    }
}