1, Stacks and queues

Topic 1: using fixed size array to realize stack and queue

Fixed size array implementation stack

public class StackWithArray {
    private int[] array;
    private int index;      //Point to the location to be placed
    public StackWithArray(int initialSize){
       if(initialSize<=0){
           throw new IllegalArgumentException("Initial capacity should not be less than or equal to 0");
       }
       array=new int[initialSize];
    }

    //Push
    public void push(int obj){
        if(index==array.length){
            throw new ArrayIndexOutOfBoundsException("Stack full");
        }
        array[index++]=obj;     // index refers to the current location of data to be stored
    }

    //Stack out
    public int pop(){
        if(index==0){
            throw new ArrayIndexOutOfBoundsException("Stack space");
        }
        return array[--index];      // The previous element pointed to by index is deleted, because index points to an empty location
    }

    //Pop element, but do not delete
    public int peek(){
        if(index==0){
            throw new ArrayIndexOutOfBoundsException("Stack space");
        }
        return array[index-1];      // Index does not decrease, so the elements in index position are not deleted
    }
}

Fixed size array implementation queue

public class QueueWithArray {
    private int[] array;
    private int start;      //Point to the head of the queue, the location of each element to be removed
    private int end;        //Point to the end of the queue where you want to add elements each time
    private int size;       //The number of elements in the queue, using size to realize the decoupling of start and end
    public QueueWithArray(int initialSize){
        if(initialSize<=0){
            throw new IllegalArgumentException("Initial capacity should not be less than or equal to 0");
        }
        array=new int[initialSize];
        start=0;
        end=0;
        size=0;
    }

    //Add an element
    public void push(int obj){
        if(size==array.length){
            throw new ArrayIndexOutOfBoundsException("The queue is full.");
        }
        size++;
        array[end]=obj;
        // If end points to the position of the last element in the array, you need to jump to the start position and start from the beginning
        end = end==array.length-1 ? 0:end+1;
    }

    //Take out an element
    public int pop(){
        if(size==0){
            throw new ArrayIndexOutOfBoundsException("Queue is empty");
        }
        size--;
        int temp=start;
        // If start points to the position of the last element in the array, you need to jump to the start position and start from the beginning
        start = start==array.length-1 ? 0:start+1;
        return array[temp];
    }
}

Topic 2: the stack that can return the smallest element in the stack

import java.util.Stack;

public class MyStack {
    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;

    public MyStack(){
        dataStack=new Stack<Integer>();
        minStack=new Stack<Integer>();
    }

    public void push(int obj){
        dataStack.push(obj);
        if (minStack.isEmpty()){
            minStack.push(obj);     // When the minimum stack is empty, store the data directly
        }
        if(dataStack.peek()<=minStack.peek()){
            minStack.push(obj);     // When obj is less than or equal to the minimum value in the minimum value stack, it is directly pushed into the stack
        }
        minStack.push(minStack.peek());     // Press the minimum value in the minimum value stack again
    }

    public int pop(){
        dataStack.pop();
        return minStack.pop();
    }

    public int getMin(){
        if(minStack.isEmpty()){
            throw new ArrayIndexOutOfBoundsException("Stack space");
        }
        return minStack.peek();
    }
}

Topic 3: how to implement stack structure only with queue structure?

• Principle: two queues (queue, help) can be used to implement the stack. When adding elements, the addition is always in the queue. When deleting elements, all elements before the last bit of the queue are popped up and put into the help queue, and then the last element returning to the queue is popped up (which meets the requirement of first in first out after stack), and then the help and queue pointers are exchanged
• Queue: Poll (remove and return the head of the queue), add (add an element to the end of the queue), peek (return the head of the queue without deleting)

import java.util.LinkedList;
import java.util.Queue;

public class TwoQueueWithStack {
    private Queue<Integer> queue;
    private Queue<Integer> help;

    public TwoQueueWithStack(){
        // LinkedList implements the Queue interface
        queue=new LinkedList<>();
        help=new LinkedList<>();
    }

    // Insert an element
    public void push(int obj){
        // The insert element is always inserted into the queue
        queue.add(obj);
    }

    // Delete an element
    public int pop(){
        if(queue.isEmpty()){
            throw  new ArrayIndexOutOfBoundsException("Stack space");
        }
        while(queue.size()>1){
            // Add all pop ups except the last element in the queue to help
            help.add(queue.poll());
        }
        int res=queue.poll();
        swap();
        return res;
    }

    // Pop up an element (do not delete)
    public int peek(){
        if(queue.isEmpty()){
            throw  new ArrayIndexOutOfBoundsException("Stack space");
        }
        while(queue.size()>1){
            // Add all pop ups except the last element in the queue to help
            help.add(queue.poll());
        }
        int res=queue.peek();
        help.add(res);
        swap();
        return res;
    }

    public void swap(){
        Queue<Integer> temp=queue;
        queue=help;
        help=temp;
    }
}

Topic 4: how to implement the queue structure with stack structure only?

• Principle: you can use two stacks (stack1 and stack2) to implement the queue. When you enter the stack, you put it in stack1, and when you exit the stack, you put it in stack2, so that you can change the order to first in first out (stack push,pop,peek)

• Points to note:
  1. Only when stack2 is empty can stack1 put data into stack2, otherwise the order will be disordered;
  2. If stack1 wants to put data into stack2, it must put all the data in stack1 into stack2 at one time.

import java.util.Stack;

public class TwoStackWithQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public TwoStackWithQueue(){
        stack1=new Stack<>();
        stack2=new Stack<>();
    }

    // Additive elements
    public void add(int obj){
        stack1.add(obj);
    }

    // Delete elements
    public int poll(){
        if(stack1.isEmpty()&&stack2.isEmpty()) {
            throw new ArrayIndexOutOfBoundsException("Queue is empty");
        }else if(stack2.isEmpty()){
            while (!stack1.isEmpty()){
                // If stack2 is empty, all elements in stack1 are inverted into stack2
                stack2.push(stack1.pop());
            }
        }
        // If there is an element in stack2, it pops up directly.
        // Only when stack2 is empty will data be put from stack1 to stack2, and it must be finished in one time
        return stack2.pop();
    }

    // Pop up element, do not delete
    public int peek(){
        if(stack1.isEmpty()&&stack2.isEmpty()) {
            throw new ArrayIndexOutOfBoundsException("Queue is empty");
        }else if(stack2.isEmpty()){
            while (!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
}

Two, linked list

Title 1: reverse unidirectional and bidirectional linked list

Reverse unidirectional list

**[Topic] realize the functions of reverse unidirectional list and reverse bidirectional list respectively.
[requirement] if the chain length is N, the time complexity is O(N), and the extra space complexity is O(1)

• [analysis] processing from beginning to end: disconnect the current node (head) from the next node and point to the previous node**

public class ReverseLinkedList {

   public static class Node{
       public int value;
       public Node next;

       public Node(int value){
           this.value = value;
       }
   }

   public static Node reverseLinkedList(Node head){
       if(head == null){
           return null;
       }

       Node pre = null;    // Previous node of current node
       Node next = null;   // The next node of the current node

       while(head != null){
           // First save the information of the next node of the head with next
           // Ensure that the single chain table will not be broken due to the loss of the original next node of the head node
           next = head.next;
           // After saving next, you can change the head from pointing to next to pointing to pre
           head.next = pre;
           // After head points to pre, continue to reverse the next node in turn
           // Let pre, head and next move backward one node in turn, and continue to reverse the pointer of the next node
           pre = head;
           head = next;
       }
       // If the head is null, pre is the last node. At this time, the list has been inverted. Pre is the first node of the list after inversion
       return pre;
   }
}

Reverse double linked list

• [analysis] processing from node to node: for each node, exchange its next and pre, and record the current reference (only for the last return)

public class ReverseDoubleLinkedLsit {
 
    public static class DoubleNode{
 
        int val;
        DoubleNode pre;    // Point to previous node
        DoubleNode next;   // Point to the next node
 
        public DoubleNode(int value){
            this.val = value;
        }
    }
 
    public static DoubleNode reverseDoubleLinkedList(DoubleNode head){
        if(head == null){
            return null;
        }
 
        DoubleNode tmp = null;
        DoubleNode res = null;  // res only records the head, because the head is null after the last loop, but we need to return the last non null head
 
        // Start from the first node and deal with it one by one
        while(head != null){
            // Exchange of pre and next pointers
            tmp = head.next;
            head.next = head.pre;
            head.pre = tmp;
            res = head;     // Record head node
            head = tmp;     // Move forward one node
        }
        return res;
    }
}

Title 2: give the head nodes of two ordered linked lists and print out the same elements in two linked lists

Similar to "Dutch flag"

public class PrintCommonPart {
 
    public static class Node{
        int value;
        Node next;
 
        public Node(int value){
            this.value = value;
        }
    }
 
    public void printCommonPart(Node head1, Node head2){
        while (head1.next != null && head2.next != null){
            if(head1.value < head2.value){
                head1 = head1.next;   // List 1 go back
            }else if(head1.value > head2.value){
                head2 = head2.next;   // List 2 go back
            }else{
                // head1.value = head2.val
                System.out.print(head1.value + " ");
                // Head 1 and head 2 go backward at the same time, and continue to find the same place
                head1 = head1.next;
                head2 = head2.next;
            }
        }
    }
}

Topic 3: judge whether a linked list is palindrome structure

Title: given the header node head of a linked list, please judge whether the linked list is palindrome structure (left and right symmetry). For example: 1 - > 2 - > 1, return true. 1 - > 2 - > 2 - > 1, return true. 15 - > 6 - > 15, return true. 1 - > 2 - > 3, return false.

Advanced: if the chain length is N, the time complexity reaches O(N), and the extra space complexity reaches O(1).

Analysis:

• Method 1: only the last half of the data is stored in the stack, and then pop up one by one to compare with the first half of the list. Space complexity is halved.
• Method 2: the spatial complexity O(1), generally, is to find the midpoint of the list, then reverse the second half, and then compare before and after, the same is palindrome. The fast pointer (two steps at a time) and the slow pointer (one step at a time) are used to find the midpoint. If they are even, the slow pointer points to the previous one of the two midpoint. If they are odd, the slow pointer points to the middle position. After judging the palindrome, you need to reverse the second half of it. You can't say that the data given to you by others, you have changed the structure to others.

    // Method 2: fold the list in half, reverse the list in the second half and compare it with the list in the first half
    public boolean isPalindromList2(Node head){
        if(head == null || head.next == null){
            return true;  // If there is no node or only one node, it must be palindrome list
        }
 
        Node cur = head;
        Node slow = head;  // Slow pointer: one node at a time
        Node fast = head;  // Fast pointer: two nodes at a time
 
        // When the total number of elements is odd, the slow pointer finally points to the middle position. If it is even, it will go to the front of the middle position
        // Note: when traversing backward, it is necessary to determine whether the node pointed by the fast pointer is empty, or an exception will occur
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next; // If fast. Next! = null, then this is even
            slow = slow.next;
        }
 
        // slow reaches the midpoint, reverses the second half, and points to null
        Node end = reverseSingleList(slow);
        fast = end;
        // Fold and contrast the front half with the back half
        while(cur != null && fast != null){
            if(cur.val != fast.val){
                return false;
            }
            cur = cur.next;
            fast = fast.next;
        }
        // The original data structure cannot be changed, so the second half needs to be reversed to restore the past
        cur = reverseSingleList(end);
        return true;
    }
 
    // Linked list inversion
    public Node reverseSingleList(Node head){
        Node pre = null;
        Node next = null;
 
        while(head != null){
            next = head.next;
            head.next = pre;
            // Move forward one node
            pre = head;
            head = next;
        }
        return pre;
    }
}

Topic 4: divide the unidirectional linked list into small on the left, equal in the middle and large on the right according to a certain value

[Topic] given the head node of a one-way linked list, the value type of the node is integer, and then given an integer pivot. Realize a function to adjust the linked list. The left part of the linked list is the node whose value is less than pivot, the middle part is the node whose value is equal to pivot, and the right part is the node whose value is greater than pivot. In addition to this requirement, there are no more requirements for the adjusted node order. For example: List 9 - > 0 - > 4 - > 5 - > 1, pivot=3. After adjustment, the chain list can be 1 - > 0 - > 4 - > 9 - > 5, or 0 - > 1 - > 9 - > 5 - > 4. In a word, the left part is less than 3 nodes, the middle part is equal to 3 nodes (this part is empty in this case), and the right part is more than 3 nodes. There is no requirement for the node order within a certain part.
Advanced: add the following two requirements to the requirements of the original problem.

The sequence requirements are also made in the left, middle and right parts. The order of nodes in each part from left to right is the same as that in the original linked list. For example: List 9 - > 0 - > 4 - > 5 - > 1, pivot=3. The adjusted list is 0 - > 1 - > 9 - > 4 - > 5. While meeting the requirements of the original problem, the left nodes are 0 and 1 from left to right. In the original list, 0 appears first, followed by 1. In this case, the middle part is empty and will not be discussed. In the right part, the nodes are 9, 4 and 5 from left to right. In the original list, 9 appears first, then 4, and finally 5.
If the chain length is N, the time complexity is O(N), and the extra space complexity is O(1).

[analysis]:

• listPartition1 non advanced version: stability and space complexity are not considered. So you can traverse the list once and store it in the array, and then the Dutch flag problem. Divide the array into three segments, less, equal, more, and then transfer the data to the list.
• Advanced version of listPartition2: stability and spatial complexity O(1) are required. When traversing the linked list, less, equal and more point to the nodes they first appear. Use endless, equal and endmore to add nodes, which one belongs to is added behind the tail [ensuring stability, because less, equal and more point to the first one in their respective range], and finally, less It's OK to link three linked lists, namely, equa and more.

Basic code:

public class LinkedPartition {
 
    public static class Node{
        int val;
        Node next;
 
        public Node(int val){
            this.val = val;
        }
    }
 
    // Put the elements in the linked list into the array first, and then divide them
    public Node listPartition1(Node head, int num){
        if(head == null || head.next == null){
            return head;
        }
 
        int i = 0;
        Node cur = head;
 
        // Calculate how many nodes there are
        while(cur != null){
            i++;
            cur = cur.next;
        }
 
        int[] arr = new int[i];   // Apply for an array equal to the number of elements in the linked list
 
        cur = head;
        i = 0;
        // Traverse from the node in the chain header, and store the val of the node in the array
        while(cur != null){
            arr[i++] = cur.val;
            cur = cur.next;
        }
        // In the array, the Dutch flag is used to divide the value into small, equal and large regions
        arrPartition(arr, num);
 
        // String the corresponding val nodes according to the ordered array order
        cur = head;
        i = 0;
        while(cur != null){
            cur.val = arr[i++];
            cur = cur.next;
        }
        return head;
    }
 
    public void arrPartition(int[] arr, int num){
        int less = -1;
        int more = arr.length;
        int cur = 0;
        while(cur != more){
            if(arr[cur] < num){
                // The current number is exchanged with a position element after the minimum area boundary, and the cur pointer advances one bit
                swap(arr, ++less, cur++);
            }else if(arr[cur] > num){
                // The current number is exchanged with the previous position element of the maximum area boundary, and the cur pointer remains unchanged
                swap(arr, cur, --more);
            }else{
                cur++;   // When equal to, cur increases automatically
            }
        }
 
    }
 
    public void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

Advanced Code:

public class LinkedPartitionImproved {
 
    public static class Node{
        int val;
        Node next;
 
        public Node(int val){
            this.val = val;
        }
    }
 
    // Will one
    public Node listPartition2(Node head, int num){
        Node less = null;       // Store nodes smaller than num, pointing to the nodes that first appear in the area
        Node equal = null;
        Node more = null;
        Node endless = null;
        Node endequal = null;   // Point to the end of each linked list
        Node endmore = null;
        Node next = null;
 
        while(head != null){
            next = head.next;
            head.next = null;  // Each node added points to null, which is the end node of less, equal and more
            if(head.val < num) {
                // Put in less area
                if (less == null) {
                    less = head;
                    endless = head;
                } else {
                    endless.next = head;   // Tail node pointer of less area points to head
                    endless = head;        // Push the list forward and point the endless pointer to the head node
                }
            }else if(head.val > num){
                // Put it in the more area
                if(more == null){
                    more = head;
                    endmore = head;
                }else{
                    endmore.next = head;
                    endmore = head;
                }
            }else{
                if(equal == null){
                    equal = head;
                    endequal = head;
                }else{
                    endequal.next = head;
                    endequal = head;
                }
            }
            head = head.next;
        }
 
        // String the three parts of the sub linked list and return
        // It is necessary to consider that some parts of the sub linked list may not exist
        if(less != null){
            endless.next = equal;     // less child list exists
            if(equal != null){
                endequal.next = more; // equal child list exists
            }else{
                endless.next = more;  // equal child list does not exist
            }
            return less;
        }else{
            // less child list does not exist
            if(equal != null){
                endequal.next = more;
                return equal;
            }else{
                // equal child list does not exist, directly return more child list
                return more;
            }
        }
    }
}

Topic 5: copy the linked list with random pointer nodes

[Topic] a special link list node class is described as follows:
public class Node {
public int value;
public Node next;
public Node random;
public Node(int data) {
this.value = data;
}
}
The value in the Node class is the Node value. The next pointer, like the next pointer in the normal single chain table, points to the next Node. The random pointer is a new pointer in the Node class. This pointer may point to any Node in the chain table or null. Given the head Node of an acyclic single chain table composed of Node node type, please implement a function to complete the replication of all structures in the chain table, and return the head Node of the new chain table.

Advanced: no additional data structure is used, only a limited number of variables are used, and the function to be realized in the original problem is completed within the time complexity of O(N).

[analysis]:

• copyListWithRand1 non advanced version: A hashmap is used to map the original linked list node and the copied node, and then the structure relationship can be copied down. To know the corresponding relationship between nodes in the replication chain, you can find it by looking up the relationship between the original nodes. For example: to get the relationship between A 'and B', you can find B through A, and then B.get() finds B '.
• copyListWithRand2 advanced version: because it is not required to use additional data structure, that is, hashmap cannot be used, only linked list is used. The steps are as follows:
  1. Copy the node to the linked list as 1 - > 1 - > 2 - > 2 - > 3 - > 3 - > 3 ->Null form;
  2. Copy rand structure
  3. Split the linked list to get the original linked list and the copied linked list.

Non advanced code implementation:

public class CopyListWithRandom {
 
    public static class Node{
        int value;
        Node next;
        Node random;    // Point to any node in the linked list or null
 
        public Node(int value){
            this.value = value;
        }
    }
 
    // hashmap is used to map element list nodes and replication nodes. key stores the original node and value stores the corresponding replication node
    public Node copyListWithRandom1(Node head){
        // Both the key and value of hashmap store Node types
        HashMap<Node,Node> map = new HashMap<Node, Node>();
 
        Node cur = head;
        // First traversal: copy nodes to form the mapping relationship between nodes
        while(cur != null){
            map.put(cur, new Node(cur.value));
            cur = cur.next;
        }
 
        cur = head;
        // Second traversal: copies the relationship between nodes, that is, next and random pointers
        // For example, if you want to know the relationship between A 'and B', you can find B 'by: A - > b - > b'
        while(cur != null){
            // The next pointer of the value node whose key is cur points to the value node whose key is cur.next
            map.get(cur).next = map.get(cur.next);
            // The random pointer of the value node whose key is cur points to the value node whose key is cur.random
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);  // Return the head node of the copied list
    }
}

Advanced code implementation:

public class CopyListWithRandomImproved {
 
    public static class Node{
        int value;
        Node next;
        Node random;    // Point to any node in the linked list or null
 
        public Node(int value){
            this.value = value;
        }
    }
 
    public Node copyListWithRandom2(Node head){
        if(head == null){
            return null;
        }
 
        Node cur = head;
        Node tmp = null;
        // Copy the node and rebuild the link list structure as follows: 1 - > 1 '- > 2 - > 2' - > 3 - > 3 '-... - > null
        // Associate the copied node directly to the next pointer of the original node
        while(cur != null){
            tmp = head.next;                 // First, save the next node in the original linked list of the current pointer
            cur.next = new Node(cur.value);  // Set the node copied by the current node as the next node of the current node
            cur.next.next = tmp;             // Set the next node of the original node as the next node of the copy node of the member node
            cur = cur.next.next;
        }
 
        cur = head;
        Node curCopy = head.next;
        // Copy random structure
        while(cur != null){
            curCopy = cur.next;
            // The random node of the copy node is the next node of the random node of cur
            curCopy.random = (cur.random == null) ? null : cur.random.next;
            cur = cur.next.next;
        }
 
        Node headCopy = head.next;
        cur = head;
        // Split list
        while(cur != null){
            curCopy = cur.next;
            cur.next = cur.next.next;   // Two next
            curCopy.next = curCopy.next == null ? null : curCopy.next.next;
            cur = cur.next;  // Propulsion node
        }
        return headCopy;
    }
}

Topic 6: a series of problems about the intersection of two single chain tables

[Topic] in this question, a single chain table may or may not have rings. Given the head nodes head1 and head2 of two single linked tables, the two linked tables may or may not intersect. Please implement a function. If two linked lists intersect, please return the first node intersected; if not, return null.
Advanced: Requirements: if the length of chain table 1 is N, the length of chain table 2 is M, the time complexity should reach O(N+M), and the additional space complexity should reach O(1).

Note: the intersection of two nodes refers to the equal memory address, not the equal value.

[analysis]: this question is actually a synthesis of three questions. To solve the following three problems: [the following is the basic version, the advanced version (without using HashSet)]

• (1) If there is a ring in a single chain table, it will return to the ring node if there is a ring, otherwise null
• (2) , whether two acyclic single chain tables intersect or not. If they intersect, the first node of the intersection will be returned. Otherwise, null
• (3) , whether two linked single linked lists intersect or not. If they intersect, the first node that intersects will be returned. Otherwise, null
  Main function:

public class FindFirstIntersectNode {
 
    public static class Node{
        int value;
        Node next;
 
        public Node(int value){
            this.value = value;
        }
    }
 
    // Main function
    public Node findFirstIntersectNode(Node head1, Node head2){
        if(head1 == null || head2 == null){
            return null;
        }
 
        // Determine whether a single chain table has rings. If there are rings, return to the ring node. Otherwise, return null
        Node loop1 = getLoopNode(head1);
        Node loop2 = getLoopNode(head2);
 
        if(loop1 == null && loop2 == null){
            // Judge whether two acyclic linked lists intersect. If they intersect, the first node intersects. If they don't, null is returned
            return noLoop(head1, head2);
        }else if(loop1 != null && loop2 != null){
            // Judge whether two linked lists intersect. If they intersect, return the intersecting node. Otherwise, return null
            return bothLoop(head1, loop1, head2, loop2);
        }
        return null;  // If a ring and a acyclic cannot intersect, null will be returned directly
    }
}

• If there is a ring in a single chain table, it will return to the ring node if there is a ring, otherwise null

  • Idea 1: use hashset to store the traversed nodes. Before each storage, first query whether the given node exists. If it exists, there is a ring;

  • Train of thought 2: use two hands, fast hands go two steps at a time, slow hands go one step at a time. When the two pointers meet, the fast pointer will return to the starting point one step at a time, and the slow pointer will continue to move one step further at the node where they meet, and will meet at the entry node of the ring.

// 1. Check whether the single chain table has rings: use the HashSet de duplication feature to complete
public Node getLoopNode(Node head){
    HashSet<Node> set = new HashSet<>();
    while(head != null){
        if(!set.contains(head)){
            set.add(head);     // If the head node is not in the set, add
            head = head.next;  // Push back the list
        }else{
            // This shows that the head node already exists in the set, that is, there is a ring, and this node is the entry node of the ring
            return head;
        }
    }
    return null;
}

• Whether two acyclic single linked lists intersect

// 2. Whether two acyclic single linked lists intersect or not. If they intersect, the first node that intersects will be returned. If they do not intersect, null will be returned
public Node noLoop(Node head1, Node head2){
    HashSet<Node> set = new HashSet<>();
    // Put head1 linked list into set
    while(head1 != null){
        set.add(head1);
        head1 = head1.next;
    }
    // Traverse the head2 linked list and compare it with the nodes of the head1 linked list in the set set set to see if there are equal
    while(head2 != null){
        if(set.contains(head2)){
            return head2;
        }
        head2 = head2.next;
    }
    return null;   // After traversing head2, there are no duplicate nodes with head1, indicating that they do not intersect
}

• Whether two linked and single linked lists intersect

// 3. whether the two linked lists intersect
public Node bothLoop(Node head1, Node loop1, Node head2, Node loop2){
    // Out of Ring Intersection: it can be reduced to finding the intersection point of acyclic single chain table
    if(loop1 == loop2){
        HashSet<Node> set = new HashSet<>();
        while(head1 != loop1){
            // Traverse nodes outside the head1 ring
            set.add(head1);
            head1 = head1.next;
        }
        while(head2 != loop2){
            // Compare the nodes outside the head2 ring with those outside the head1 ring to see if they are equal
            if(set.contains(head2)){
                return head2;
            }
            head2 = head2.next;
        }
        return loop1;
    }else{
        // Two 6 forms of no intersection + intersection within the ring (different ring entry points)
        Node cur = loop1.next;
        while(cur != loop1){
            // cur starts from loo1 and traverses down in the ring. If it does not encounter loop2 until it traverses to the location of loop1 again, it means that they do not intersect
            if(cur == loop2){
                return loop1;   // If you meet loop2, it means that the intersection is the case of the intersection in the ring
            }
            cur = cur.next;
        }
        return null;  // cur doesn't encounter loop2 after traversing its own ring, which means that it doesn't intersect, that is, two sixes
    }
}

3, Matrix printing and rotation

Topic 1: clockwise printing matrix

Idea: the upper left corner element and the lower right corner element can form a matrix. Each print is from the top left corner. After printing the outer circle, print the inner circle.

public class PrintMatrix {
 
    public void printMatrix(int[][] matrix){
        int lr = 0;
        int lc = 0;
        int rr = matrix.length - 1;
        int rc = matrix[0].length - 1;
 
        // Stop printing when the abscissa in the upper left corner is greater than or equal to the abscissa in the lower right corner
        while(lr <= rr && lc <= rc){
            printEdge(matrix, lr++, lc++, rr--, rc--);
        }
    }
 
    /**
     * Print four edges: boundary processing + four while loops
     * @param matrix: matrix
     * @param lr: Top left element abscissa
     * @param lc: Top left element ordinate
     * @param rr: Bottom right element abscissa
     * @param rc: Bottom right element ordinate
     */
    public void printEdge(int[][] matrix, int lr, int lc, int rr, int rc){
        if(lr == rr){
            // If lr == rr: it means that there is only one line of data, then only one line of data can be printed
            for(int i = lc; i <= rc; i++){
                System.out.print(matrix[lr][i] + " ");
            }
        }else if(lc == rc){
            // If lc == rc: it means that there is only one column of data, only this column of data can be printed
            for(int i = lr; i <= rr; i++){
                System.out.print(matrix[lc][i] + " ");
            }
        }else{
            int curC = lc;
            int curR = lr;
            while (curC != rc){
                // Print overline
                System.out.print(matrix[lr][curC] + " ");
                curC++;
            }
            while (curR != rr){
                // Print right vertical line
                System.out.print(matrix[curR][rc] + " ");
                curR++;
            }
            while(curC != lc){
                // Print bottom horizontal line
                System.out.print(matrix[rr][curC] + " ");
                curC--;
            }
            while(curR != lr){
                // Print left vertical line
                System.out.print(matrix[curR][lc] + " ");
                curR--;
            }
        }
    }
 
    // test
    public static void main(String[] args){
        PrintMatrix pm = new PrintMatrix();
        int[][] matrix = {{1,2,3},{4,5,6},{7,8,9}};
        pm.printMatrix(matrix);
    }
}

Topic 2: turn a square 90 degrees clockwise

Thinking: [macro] drawing + boundary conditions.

    public int[][] rotateMatrix(int[][] matrix){
        if(matrix.length != matrix[0].length){
            throw new IllegalArgumentException("error : the input is error!");
        }
 
        int lr = 0;
        int lc = 0;
        int rr = matrix.length - 1;
        int rc = rr;
 
        while(lr < rr){
            rotateEdge(matrix, lr++, lc++, rr--, rc--);
        }
        return matrix;
    }
 
    /**
     * Rotate a square circle 90 degrees
     * @param matrix: Square
     * @param lr: Line number in the upper left corner
     * @param lc: Column number in the upper left corner
     * @param rr: Line number in the lower right corner
     * @param rc: Column number in the lower right corner
     */
    public void rotateEdge(int[][] matrix, int lr, int lc, int rr, int rc){
        int times = rc - lc;   // Number of rotations = rows / columns - 1
        int tmp = 0;
        // Change the positions of four points, and turn them anticlockwise
        for(int i = 0; i != times; i++){
            tmp = matrix[lr][lc + i];
            matrix[lr][lc + i] = matrix[rr - i][lc];   // Replace the position element of the upper horizontal line with the position element of the left vertical line
            matrix[rr - i][lc] = matrix[rr][rc - i];   // Replace the position element of the left vertical line with the position element of the lower horizontal line
            matrix[rr][rc - i] = matrix[lr + i][rc];   // Replace the position element of the lower horizontal line with the position element of the right vertical line
            matrix[lr + i][rc] = tmp;                  // Replace the position element of the right vertical line with the position element of the upper horizontal line
        }
    }
 
    // test
    public static void main(String[] args){
        RotateMatrix rm = new RotateMatrix();
        int[][] matrix = new int[][]{{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
        int[][] res = rm.rotateMatrix(matrix);
        for(int i = 0; i < res.length; i++){
            for(int j = 0; j < res[0].length; j++){
                System.out.print(res[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Topic 3: zigzag printing matrix

[Topic] given a matrix, print it in zigzag form, for example:
1 2 3 4
5 6 7 8
9 10 11 12
The results of zigzag printing are: 1, 2, 5, 9, 6, 3, 4, 7, 10, 11, 8, 12
[requirement] the additional space complexity is O(1).

[analysis]: from a macro point of view, it is also considered as continuous printing of slashes. Every time a slash is printed, the next slash will be printed in a different direction
At the beginning, A (row2, coll2) and B (row, Coll) are located at (0,0), then A goes to the right, goes down at the end, and B goes down at the same time, goes to the right at the end, when both go to the bottom right corner of the end, all printing ends.

public class PrintZigMatrix {
 
    public void printZigMatrix(int[][] matrix){
        // Two ends of each printing track: A(a,b) B(c,d)
        int a = 0, b = 0, c = 0, d = 0;
        // Coordinates of the lower right corner of the matrix: (endRow,endCol)
        int endRow = matrix.length - 1;
        int endCol = matrix[0].length - 1;
 
        // Determine the direction of each printing, and change direction every time
        boolean direction = true;
 
        // A is to go first to the right and then to the right; B is to go first and then to the right
        while (a <= endRow && b <= endCol){
            printSlash(matrix, a, b, c, d, direction);
            direction = !direction;  // Commutation
            // If a goes to the far right, he starts to go down. b must be below a, because the change of b value will directly affect a
            a = b >= endCol ? a + 1 : a;
            b = b < endCol ? b + 1 : b;
 
            // If B goes to the bottom, it starts to go to the right. c must be below d, because the change of c value will directly affect d
            d = c >= endRow ? d + 1 : d;
            c = c < endRow ? c + 1 : c;
        }
    }
 
    // Print the track between points A and B
    public void printSlash(int[][] matrix, int a, int b, int c, int d, boolean direction){
        // When the direction is true, it is printed from bottom to top, that is, B -- > A
        if(direction){
            for(; a <= c; c--, d++){
                System.out.print(matrix[c][d] + " ");
            }
        }else{
            for(; a <= c; a++, b--){
                System.out.print(matrix[a][b] + " ");
            }
        }
    }
 
    // test
    public static void main(String[] args){
        PrintZigMatrix pzm = new PrintZigMatrix();
        int[][] matrix = new int[][]{{1,2,3,4},{5,6,7,8},{9,10,11,12}};
        pzm.printZigMatrix(matrix);  // 1 2 5 9 6 3 4 7 10 11 8 12 
    }
}

Question 4: find out whether a number exists in the matrix of m rows and n columns with ordered rows and columns

The required time complexity is O(m+n)
[analysis]: the query starts from the last number in the first row. The current query number is recorded as a(i,j). Because it is ordered, so:

• If a < K, the number of a on the left side of the line must be less than k, so a moves down;
• If a > k, then the number under the column a must be greater than k, so a moves to the left;
• Otherwise, a = k, return true;
• If no matrix is returned after checking, it means that k is not in the matrix, and false is returned.

public class SearchInSortedMatrix {
 
    public boolean search(int[][] matrix, int k){
        int i = 0;
        int j = matrix[0].length - 1;
 
        // Search from top right
        while(i < matrix.length && j > -1){
            if(matrix[i][j] < k){
                // If the matrix[i][j] is less than k, look under the matrix[i][j]
                i++;
            }else if(matrix[i][j] > k){
                // matrix[i][j] if it is greater than k, find it on the left side of matrix[i][j]
                j--;
            }else{
                return true;   // matrix[i][j] = k
            }
        }
        return false;
    }
 
    // test
    public static void main(String[] args){
        SearchInSortedMatrix search = new SearchInSortedMatrix();
        int[][] matrix = new int[][]{{0,1,2,5},{2,3,4,7},{4,4,4,8}};
        Boolean res = search.search(matrix, 8);
        System.out.print(res);
    }
}