【算法训练-链表 三】【特殊链表】环形链表、环形链表II、回文链表、相交链表

import java.util.*;
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        // 1 当链表尾null直接返回false
        if (head == null) {
            return false;
        }
        // 2 定义快慢指针，快指针每次走两步，慢指针每次走一步
        ListNode fast = head;
        ListNode slow = head;
        // 3 直到快指针到链表结尾如果快慢还没有相遇则无环
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 如果中途相遇，则有环，停止遍历，直接返回
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
}

a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode p1 = pHead;
        ListNode p2 = pHead;
        // 1 如果存在碰撞点，则证明链表有环，将p2设置到碰撞点
        if (getCrashNode(pHead) != null) {
            p2 = getCrashNode(pHead);
        } else {
            // 2 如果不存在碰撞点，则证明链表无环，直接返回null
            return null;
        }
        // 3 节点相交位置即是环入口节点，当然p2可能会经过N圈
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
    // 获取换节点碰撞点
    private ListNode getCrashNode(ListNode pHead) {
        ListNode fast = pHead;
        ListNode slow = pHead;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                return fast;
            }
        }
        return null;
    }
}

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // 1 判断入参，如果是空链表，返回false
        if (head == null) {
            return false;
        }
        // 2 定义快慢指针，快指针每次两步，到结尾时，慢指针刚好到中间
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 如果fast不为null，则链表长度为奇数，且slow位于中点，中点不用判断，所以slow应该向后移一位
        if (fast != null) {
            slow = slow.next;
        }
        // 3 反转后半段回文链表，并且slow指向后半部分头部、fast回到头部，两个链表继续向后
        slow = reverse(slow);
        fast = head;
        while (slow != null) {
            if (slow.val != fast.val) {
                return false;
            } else {
                fast = fast.next;
                slow = slow.next;
            }
        }
        return true;
    }
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode pNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = pNext;
        }
        return pre;
    }
}

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        // 1 定义双指针分别指到链表头节点
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        // 2 相等时结束循环，可能是相交节点，也可能是null
        while (p1 != p2) {
            p1 = p1 == null ? pHead2 : p1.next;
            p2 = p2 == null ? pHead1 : p2.next;
        }
        // 3 相交节点或null都满足题目要求：如果无相交节点则返回空
        return p1;
    }
}