链表算法 篇三

package com.algorithm202305.linkedlist;

/**
 * https://leetcode.cn/problems/middle-of-the-linked-list/submissions/432318762/
 * 单链表的中点
 * 问题的关键也在于我们无法直接得到单链表的长度 n，常规方法也是先遍历链表计算 n，再遍历一次得到第 n / 2 个节点，也就是中间节点。
 *
 * 如果想一次遍历就得到中间节点，也需要耍点小聪明，使用「快慢指针」的技巧：
 *
 * 我们让两个指针 slow 和 fast 分别指向链表头结点 head。
 *
 * 每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。
 */
public class Demo5 {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

    }
    ListNode middleNode(ListNode head){
        //快慢指针指向head
        ListNode slow = head,fast = head;
        while (slow != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

package com.algorithm202305.linkedlist;

/**
 * 1 判断链表是否成环（环形链表）
 * https://leetcode.cn/problems/linked-list-cycle/
 * 2 环的起点（环形链表Ⅱ）
 * https://leetcode.cn/problems/linked-list-cycle-ii/
 * 判断链表是否包含环属于经典问题了，解决方案也是用快慢指针：
 * 
 */
public class Demo6 {
    class ListNode {
        int val;
        ListNode next;
    }

    boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (slow != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            //fast有是slow的两倍速存在环应该有相等的节点
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
    //环的起点
    public ListNode detectCycle(ListNode head) {
        ListNode fast, slow;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        if(fast == null || fast.next == null){
            return null;
        }
        //慢指针重新指向头节点
        slow = head;
        //快指针比慢指针要比慢指针多走K步，设置起点距离相遇点是m步，那么对于k-m就是环起点
        while (slow != fast){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

package com.algorithm202305.linkedlist;

/**
 * 两链表是否有相交（相交链表）
 * https://leetcode.cn/problems/intersection-of-two-linked-lists/
 */
public class Demo7 {
    class ListNode {
        int val;
        ListNode next;
    }
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // p1 指向 A 链表头结点，p2 指向 B 链表头结点
        ListNode p1 = headA, p2 = headB;
        while (p1 != p2) {
            // p1 走一步，如果走到 A 链表末尾，转到 B 链表
            if (p1 == null) p1 = headB;
            else            p1 = p1.next;
            // p2 走一步，如果走到 B 链表末尾，转到 A 链表
            if (p2 == null) p2 = headA;
            else            p2 = p2.next;
        }
        return p1;
    }

}