1. Determine if a list of chains is palindromic (the same from forward to backward and from backward to forward)

Solution 1: Traverse the entire list with one stack (the extra space is O(N), save the values of the list in the stack, pop them out one by one, and compare them with the values of the list.

Solution 2: (Extra space is O(N/2)) Set a fast pointer n1 and a slow pointer n2, the fast pointer takes two steps, the slow pointer takes one step, and when the fast pointer reaches the end, the slow pointer just goes to the middle (odd number) or the first (even number) in the middle.

        Node n1 = head;
        Node n2 = head;
        while(n2.next!=null&&n2.next.next!=null){
            n1 = n1.next;
            n2 = n2.next.next;
        }

Put the numbers to the right on the stack, and then compare the start with the stack pop until the stack is empty.

        while(!stack.isEmpty()){
            if(stack.pop()!=head.val){
                return false;
            }
            head = head.next;
        }

Solution 3: (Extra space is O(1)), the previous stage is similar to Solution 2.

Point the intermediate element node to empty, with the stack on the right reversed.n3 is the next number, n2 is itself, n1 is the last number

        n2 = n1.next;
        n1.next =null;
        Node n3 =null;
        while(n2!=null){
            n3 = n2.next;
            n2.next = n1;
            n1 = n2;
            n2 = n3;
        }

Then go left to right, right to left

        n3 = n1;
        n2 = head;
        while(n2!=null){
            if(n2.val!=n1.val){
                flag = false;
                break;
            }
            n2 = n2.next;
            n1 = n1.next;
        }

After that, adjust the stack, think, get out of the way, n3 saves the last number, n2 saves the next number, n1 is itself

        n1 = n3.next;
        n3.next =null;
        while(n1!=null){
            n2 = n1.next;
            n1.next =n3;
            n3 = n1;
            n1 = n2;
        }

2. Divide a one-way chain table into small on the left, equal in the middle, and large on the right by a certain value

Solution: Save the node in an array, divide it by the Dutch flag method according to the value of the node (with the help of x, y variables, both sides encapsulated), and then let the next of the node point to the next array.(The solution is not stable and the additional spatial complexity is O(N))

2.1 Advancement: Satisfies stability and additional spatial complexity with O(1)

2.1.1 sets three parts, expressed as less than, equal to, greater than;

2.1.2 Set two variables for each section, head and tail;

2.1.3 Traverse the list of chains into three parts; disconnect first during the traversal process;

2.1.4 connects the small tail with the equal head and the equal tail with the larger head.

2.1.5 This list is stable.

3. Copy the chain table with random pointer nodes (Node has both next and random)

(Extra spatial complexity O(N))

3.1 First use HashMap to copy nodes of a node (only contain val, (next, random does not point)

HashMap<Node,Node> map = new HashMap<>();
Node n1 = head;
while(n1!=null){
      map.put(n1,new Node(n1.value));
      n1 = n1.next;
}

3.2 Connect the next and random relationships and copy the relationships of the copied chains using the original chains

        n1 = head;
        while(n1!=null){
            map.get(n1).next = map.get(n1.next);
            map.get(n1).rand = map.get(n1.rand);
            n1 = n1.next;
        }

(Extra spatial complexity O(1))

3.1 First insert a replication node in the original list, such as 1-1'-2'-3-3'

        while(cur!=null){
            copy = new Code_13_CopyListWithRandom.Node(cur.value);
            next = cur.next;
            cur.next = copy;
            copy.next = next;
            cur = next;
        }

3.2 assigns random to the replication node, that is, the replication node's random is the next random to the original node.

        cur = head;
        while(cur!=null){
            cur.next.rand = cur.rand==null?null:cur.rand.next;
            cur = cur.next.next;
        }

3.3 Separate the replicated list from the original list, keeping the next node before disconnecting.

        cur = head;
        next = null;
        copy =null;
        copy1 = head.next;
        while(cur!=null&&cur.next!=null){
            next=cur.next.next;
            copy = cur.next;
            cur.next = next;
            copy.next = next==null?null:next.next;
            cur = next;
        }

4. [Title] In this topic, a single-chain list may or may not have rings.Given the header nodes head1 and head2 of two single-chain lists, they may or may not intersect.Implement a function that returns the first node that intersects if two lists of chains intersect, or null if they do not.Requirements: If the length of Chain Table 1 is N, the length of Chain Table 2 is M, the time complexity should be O(N+M), and the extra space complexity should be O(1)

4.1 First determine whether the list is looped or not, use HashSet to store the nodes, then iterate through the list to see if there are any nodes in the HashSet.

    public Node getLoopNode(Node head) {
        if(head.next==null||head.next.next==null){
            return null;
        }
        HashSet<Node> set = new HashSet<>();
        while(head!=null){
            if(set.contains(head)){
               return head;
            }
            set.add(head);
            head = head.next;

        }
        return null;
    }

4.2 You can also use the fast pointer and the slow pointer to determine whether the chain list has rings or not. If there are rings, then the speed must meet. After encountering, let the fast pointer go back to the beginning and take one step at a time. The point where the speed meets is the point into the ring.

    public static Node getLoopNode1(Node head) {
        if(head==null||head.next==null||head.next.next==null){
            return null;
        }
        Node fast = head.next.next;
        Node slow = head.next;
        while(fast!=slow){
            if(fast.next==null||fast.next.next==null){
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = head;
        while(fast!=slow){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

4.3 When two acyclic chains intersect, the first list can be saved in a HashSet and then the second list can be traversed, or if a node exists in a HashSet, the first intersecting node

    public static Node noLoop(Node head1, Node head2) {
        HashSet<Node> set = new HashSet<>();
        while(head1!=null){
            set.add(head1);
            head1 = head1.next;
        }
        while (head2!=null){
            if(set.contains(head2)){
                return head2;
            }
            head2 = head2.next;
        }
        return null;
    }

4.4 Two acyclic chains intersect, traverse the chains table 1, save the length of the chains table and the last node, traverse the chains table 2, save the length of the chains table and the last node, if there is an intersection, then the ends of the two chains must be equal.Make decisionsThen calculate the difference based on the length, letting the length take the difference step first, then walk together, or if the same, the first intersecting node.

    public static Node noLoop1(Node head1, Node head2) {
        Node n1 = head1;
        Node n2 = head2;
        int len =0;
        while(n1!=null){
            len++;
            n1 = n1.next;
        }
        while(n2!=null){
            len--;
            n2 = n2.next;
        }
        if(n2!=n1){
            return null;
        }
        n1 = len>0?head1:head2;
        n2 = n1==head1?head2:head1;
        len = Math.abs(len);
        while(len!=0){
            n1 = n1.next;
            len--;
        }
        while(n1!=n2){
            n1 = n1.next;
            n2 = n2.next;
        }
        return n1;
    }

4.5 One has rings and one has no rings and cannot intersect.Because tails can't touch each other.

4.6 Two rings have three structures: 1.Two do not intersect; 2.Enter the ring from the same location; 3.Enter the ring from different locations.

Determine if the entry points are equal first, or if they are equal, case 2, to find the first intersection point;

Unequal is case 1 or 3. Continue to judge, if the next entry point can be reached when the entry point moves on, it is case 3 and returns to the current node.

    public static Node bothLoop(Node head1,Node loop1, Node head2, Node loop2) {
        HashSet<Node> set = new HashSet<>();
        Node n1 = head1;
        Node n2 = head2;
        if (loop1 == loop2) {
            while (!set.contains(n1)) {
                    set.add(n1);
                n1 = n1.next;
            }
            while(n2!=null){
                if(set.contains(n2)){
                    return n2;
                }
                n2 = n2.next;
            }
            return null;
        }
        else {
            n1 = loop1.next;
            while (n1 != loop1) {
                if (n1 == loop2) {
                    return loop1;
                }
                n1 = n1.next;
            }
            return null;

        }
    }

    public static Node bothLoop1(Node head1, Node loop1, Node head2, Node loop2) {
        if(loop1==loop2){
            Node n1 = head1;
            Node n2 = head2;
            int len = 0;
            while(n1!=loop1){
                n1 = n1.next;
                len++;
            }
            while(n2!=loop2){
                n2 = n2.next;
                len--;
            }
            n1 = len>0?head1:head2;
            n2 = n1==head1?head2:head1;
            len = Math.abs(len);
            while(len!=0){
                len--;
                n1 = n1.next;
            }
            while(n1!=n2){
                n2 = n2.next;
                n1 = n1.next;
            }
            return n1;
        }
        else{
            Code_14_FindFirstIntersectNode.Node n1 = loop1.next;
            while(n1!=loop1){
                if(n1==loop2){
                    return loop1;
                }
                n1 = n1.next;
            }
        }
        return null;
    }