[数据结构与算法]04-算法训练营第四天 | 力扣24两两交换链表中的节点、力扣19删除链表的倒数第N个节点、力扣160相交链表、力扣142环形链表||

力扣24：两两交换链表中的节点

题目链接:力扣24：两两交换链表中的节点

思路：

1.需要手动去画这个过程，不然不易理解
2.定义一个虚拟头节点dummy，下一个节点指向head
3.定义一个指针cur指向虚拟头节点，用于遍历后面元素
4.将cur的下一个节点进行记录，再将cur下一个指向的指针的下一个元素记录下来
5.进行两个元素的交换

代码：

/**
 * 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) {
        // 1.定义虚拟头节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 2.定义一个指针指向虚拟头节点，用于遍历元素
        ListNode cur = dummy;

        // 3.遍历元素并开始交换
        while (cur.next != null && cur.next.next != null) {
            // 4.保存cur的下一个节点
            ListNode temp = cur.next;
            // 5.保存cur下一次指向的节点的下一个节点
            ListNode temp1 = cur.next.next.next;
            cur.next = cur.next.next;
            cur.next.next = temp;
            cur.next.next.next = temp1;
            cur = cur.next.next;
        }

        return dummy.next;
    }
}

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

题目链接:力扣19删除链表的倒数第N个节点

思路：

1.一定要手画移动过程
2.定义一个虚拟头节点，它的下一个节点指向head
3.定义两个指针，快指针和慢指针，刚开始都指向虚拟头节点
4.先移动快指针移动n步，要保证fast不为null
5.然后同时移动快慢指针，直到快指针fast指向最后一个节点
6.慢指针slow开始删除节点

代码：

/**
 * 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) {
        // 1.定义一个虚拟头节点并且下一个节点指向head
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 2.定义两个指针，分别为快慢指针，指向虚拟头节点
        ListNode fast = dummy;
        ListNode slow = dummy;

        // 3.移动快指针，移动n步
        // 因为快指针刚开始在虚拟头节点，所以需要再移动一步
        while (n != 0 && fast != null) {
            fast = fast.next;
            n--;
        }

        // 4.同时移动快慢指针
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;

        return dummy.next;
    }
}

力扣160相交链表

题目链接:力扣160相交链表

思路：

1.遍历两条链表，分别获取二者长度
2.获取二者长度差，然后将较长的节点头节点指针移动该长度差个步数
3.将另一个指针指向较短链表的头节点，然后同时移动两个指针，直到两个节点相同返回即可

代码：

/**
 * 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 lenA = 0, lenB = 0;
        while (curA != null) { // 求链表A的长度
            lenA++;
            curA = curA.next;
        }
        while (curB != null) { // 求链表B的长度
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            // 求长度差
            int gap = lenB - lenA;
            // 让curA和curB在同一起点上（末尾位置对齐）
            while (gap-- > 0) {
                curB = curB.next;
            }
            // 遍历curA 和 curB，遇到相同则直接返回
            while (curB != null) {
                if (curB == curA) {
                    return curB;
                }
                curA = curA.next;
                curB = curB.next;
            }
        } else {
            // 求长度差
            int gap = lenA - lenB;
            // 让curA和curB在同一起点上（末尾位置对齐）
            while (gap-- > 0) {
                curA = curA.next;
            }
            // 遍历curA 和 curB，遇到相同则直接返回
            while (curA != null) {
                if (curA == curB) {
                    return curA;
                }
                curA = curA.next;
                curB = curB.next;
            }
        }
        
        return null;
    }
}

力扣142环形链表||

题目链接:力扣142环形链表||

思路：

1.要先画图和推导公式，即可得出x=z
2.定义两个指针，分别为快指针和慢指针，快指针走两步，慢指针走一步
3.当快慢指针相遇的时候，分别定义两个指针指向头节点和相遇节点
4.两个新指针分别依次移动一步，直到相遇即为环形入口

代码：

/**
 * 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) {
        // 1.定义快慢指针，都指向头节点
        ListNode fast = head;
        ListNode slow = head;
        // 2.移动快指针和慢指针，快指针每次走两步，慢指针每次走一步
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 3.直到相遇
            if (fast == slow) {
                // 4.定义两个节点分别指向相遇节点和头节点
                ListNode index1 = head;
                ListNode index2 = fast;
                // 5.依次移动两个指针，每次一步，直到相遇即为环形入口
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }

        return null;
    }
}