[数据结构与算法]代码随想录算法训练营第四天

两两交换链表中的节点

题目：LeetCode.24

/**
 * 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 dummy = new ListNode();
        dummy.next = head;
        ListNode p = dummy;
        while (p.next != null && p.next.next != null){
            ListNode tmp = head.next.next;
            p.next = head.next;
            head.next.next = head;
            head.next = tmp;
            p = head;
            head = head.next;
        }
        return dummy.next;
    }
}

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

题目：LeetCode.19

双指针法，fast和slow指针保持一定距离同步向前移动至fast指针指向表尾，slow指针指向要删除节点的前一个结点，注意判断slow.next.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 removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        while (n-- > 0) {
            fast = fast.next;
        }
        while (fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }
        if(slow.next != fast){
            slow.next = slow.next.next;
        }
        else slow.next = null;
        return dummy.next;
    }
}

链表相交

题目：LeetCode.面试题.20.07

注意判断的时候应该是指针相等,而不是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 p = headA;
        ListNode q = headB;
        int lenA = 0;
        int lenB = 0;
        int cnt;

        while (p != null) { 
            lenA++;
            p = p.next;
        }
        while (q != null) { 
            lenB++;
            q = q.next;
        }
        p = headA;
        q = headB;
        if (lenA > lenB){
            cnt = lenA - lenB;
            while (cnt -- > 0){
                p = p.next;
            }
            while (p != null){
                if (p == q){
                return p;
                }
                else{
                p = p.next;
                q = q.next;
                }
            }
            return null;
        }
        else {
            cnt = lenB - lenA;
            while (cnt -- > 0){
                q = q.next;
            }
            while (p != null){
                if (p == q){
                return p;
                }
                else{
                p = p.next;
                q = q.next;
                }
            }
            return null;
        }
    }
}

环形链表Ⅱ

题目：LeetCode.142

双指针法，如果快慢指针相遇则存在环，相遇位置必然在环中的某个点。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5TxeGqtI-1664007706638)(C:\Users\19899\AppData\Roaming\Typora\typora-user-images\image-20220924160704882.png)]

相遇时，slow指针走过的节点数为: x + y（相遇时slow一定没有完整的走完一个环，而fast已经在环内，fast的相对速度为1，相遇slow时一定走的不是一个完整的环。）， fast指针走过的节点数：x + y + n (y + z)。fast走过的节点数为slow的2倍，故(x + y) * 2 = x + y + n (y + z)。整理公式之后为如下公式：x = (n - 1) (y + z) + z 。这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

/**
 * 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 slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            //存在环
            if (fast == slow){
                ListNode p = fast;
                ListNode q = head;
                while (p != q){
                    q = q.next;
                    p = p.next;
                }
                return p;
            }
        }
        return null;
    }
}