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

/**
 * 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(-1,head);
        ListNode cur = dummy.next;
        ListNode pre = dummy;
        ListNode swap = null;
 
        if (head == null || head.next == null) {
            // 链表为空或只有一个元素，直接返回
            return head;
        }
        else {
            while (cur != null && cur.next != null) {
                // 当前还剩至少2个节点，需要交换
                swap = cur.next;
                cur.next = swap.next;
                swap.next = cur;
                pre.next = swap;
                pre = cur;
                cur = cur.next;
            }
            return dummy.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,head);
        ListNode pre_delay = dummy;
        ListNode cur_delay = dummy.next;
        ListNode pre = dummy;
        ListNode cur = dummy.next;
        int delay = 1;
        if (head == null || head.next == null) {
            return null;
        }
        while (cur != null) {
            if (delay <= n) {
                delay ++;
            }
            else {
                pre_delay = cur_delay;
                cur_delay = cur_delay.next;
            }
            pre = cur;
            cur = cur.next;
        }
        System.out.println(pre_delay.val);
        pre_delay.next = cur_delay.next;
        return dummy.next;
    }
}

/**
 * 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) {
        int len_a = getLength(headA);
        int len_b = getLength(headB);
        ListNode long_list = null;
        ListNode short_list = null;
        ListNode long_cur = null;
        ListNode short_cur = null;
        int diff = 0;
 
        if (len_a > len_b) {
            long_list = headA;
            short_list = headB;
            long_cur = headA;
            short_cur = headB;
            diff = len_a - len_b;
        }
        else {
            long_list = headB;
            short_list = headA;
            long_cur = headB;
            short_cur = headA;
            diff = len_b - len_a;
        }
 
        for (int i = 0; i < diff; i++) {
            long_cur = long_cur.next;
        }
 
        while (long_cur != null) {
            if (long_cur != short_cur) {
                long_cur = long_cur.next;
                short_cur = short_cur.next;
            }
            else {
                return long_cur;
            }
        }
 
        return null;
    }
    public int getLength(ListNode head) {
        int length = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            length ++;
        }
        return length;
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode cur = head;
        Set<ListNode> past = new HashSet<ListNode>();
        
        while (cur != null) {
            if (past.contains(cur))
                return cur;
            else
                past.add(cur);
            cur = cur.next;
        }
 
        return 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 (slow == fast) {  // 有环
                ListNode cur = head;
                while (cur != slow) {
                    // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
                    cur = cur.next;
                    slow = slow.next;
                }
                return cur;
            }
        }
        return null;
    }
}