链表篇

有环链表判断，快慢指针

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

通用克隆数据结构方法

/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
    public Node copyRandomList(Node head) {
                
        if (head == null) return null;
        
        Map<Node, Node> map = new HashMap<>();
        
        // copy nodes
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        
        // copy link
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = cur.random == null ? null : map.get(cur.random);
            cur = cur.next;
        }
        
        return map.get(head);
    }
}

Tricky 方法

/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
    public Node copyRandomList(Node head) {
                
        if (head == null) return null;
        
        // Copy node and put into cur.next
        Node cur = head;
        while (cur != null) {
            Node next = cur.next;
            Node copy = new Node(cur.val);
            cur.next = copy;
            copy.next = next;
            cur = next;
        }

        // Link the random
        cur = head;
        while (cur != null) {
            cur.next.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }
        
        // Sepreate two linkedlist
        cur = head;
        Node copyHead = head.next;
        
        while (cur != null) {
            Node copy = cur.next;
            Node next = copy.next;
            cur.next = next;
            copy.next = next == null ? null : next.next;
            cur = next;
        }
        return copyHead;
    }
}