When we write the interview, we often struggle with whether to customize the linked list or initialize a linked list first. Generally not required. If it is written on white paper, the normal interviewer will define it for you. If it is a video surface, Niuke and other systems will also be defined.

What if you meet someone who has nothing? Often we are in a hurry before we start writing algorithms, and sometimes we don't even know how to write them. Therefore, in the previous section and this section, we focus on reviewing the characteristics of the linked list, and then we can define an executable structure. In the next section, we will start to analyze the algorithm.

The test questions of one-way circular linked list are not many, but they are widely used in practice, including the RingBuffer mentioned above, which can also be done with one-way circular linked list. It is also widely used in the source code of JUC and other places. And the one-way circular linked list itself can be used as the expansion and practice of the linked list. Therefore, in this section, we will sort out the relevant contents.

The pointer of the last node in the table points to the head node, and the whole linked list forms a ring. Others are the same as single linked list.

Here we use internal classes to define nodes. The code structure of this method is clearer:

public class LinkedListCircular {//Static class node {int data; node next; public node (int data) {this. Data = data;} ​        @Override        public String toString() {            return "Node{data=" + data + "}";        }    } / / initialize {public static node initlist (int n) {node head = new node (1); node current = head; for (int i = 1; I < n; I + +) {current.next = new node (2 * I + 1); current = current.next;} current. next = head;         return head;    }

At this time, if we want to create a linked list, we can write it as follows:

 Node head = initList(5);

Next, let's look at the common operations of linked lists

I lookup

Because it is a ring, we have to use a new way to judge the end of the table when traversing.

In the single linked list, we judge as follows:

while(temp.next!=null){    temp=temp.next;}

In the one-way circular linked list, we are as follows:

while(temp.next!=head){    temp=temp.next;}

So to determine the length of the linked list, we have to write this:

   /**     * Length of linked list * * @ return length of linked list     */    public static int getLength(Node head) {        if (head == null) {            return 0;        }        Node current = head;        int size = 0;        do {            size++;            current = current.next;        } while (current != head);        return size;    }

Find the node at the specified location, which is written as follows:

/**     * Find the node at the specified location * * @ param head node * @ param position the node to be found * @ return the node found     */    public static Node getNode(Node head, int position) {        if (head == null || position <= 0 || position > getLength(head)) {            System.out.println("The location of the linked list is incorrect! return null");            return null;        } else {            int count = 0;            Node node = null;            Node current = head;            do {                count++;                if (count == position) {                    node = new Node(current.data);                }                current = current.next;            } while (current != head);            return node;        }    }

If we want to find the tail node, write this:

 /**     * Find tail node * * @ param head node * @ return found node     */    private static Node getLastNode(Node head) {        Node current = head;        do {            current = current.next;        } while (current.next != head);        return current;    }

II insert

The insertion operation does not need to consider the tail and header of the table. It is handled with intermediate elements:

​    /**     * Header insert * @ param head header node * @ param insertNode node to be inserted     */    public static Node insertFirstNode(Node head, Node insertNode) {        Node lastNode = getLastNode(head);        insertNode.next = head;        //The last newly inserted node refers to the head node lastnode next = insertNode;         return insertNode;    }

The common insertion method is:

/**     * Insert * * @ param head header node * @ param insertNode node to be inserted     */    public static Node insertNode(Node head, Node insertNode) {        Node lastNode = getLastNode(head);        lastNode.next = insertNode;        //The last newly inserted node refers to the head node insertnode next = head;         return head;    }

III Delete element

The deletion operation does not need to consider the problems of footer and header. It is handled with intermediate elements:

Let's now look at a complete example:

  /**     * Delete * * @ param head header node * @ param deleteNode node node to be deleted     */    public static Node deleteNode(Node head, Node deleteNode) {        // If the head node needs to be deleted, lastnode = getlastnode (head); while (head.data == deleteNode.data) {            head = head.next;        }         lastNode. next = head;        //  Delete other nodes. Node prenode = head; Do {/ / judge whether the next node of the current node is the node to be deleted if (preNode.next.data == deleteNode.data) {/ / delete the node prenode. Next = prenode. Next. Next;} Else {/ / current pointer moves back prenode = prenode. Next;}} while (preNode.next != head);         return head;    }

Finally, write a method to print the linked list. This method is only used when you write your own handwriting. It is generally not used in LeetCode, because the system will return your results in the way of return instead of printing.

 /**     * Linked list print * * @ param head header node     */    public static String toString(Node head) {        if (head == null) {            return null;        }        int length = getLength(head);        StringBuilder sb = new StringBuilder();        Node current = head;        int count = 0;        do {            sb.append(current.data).append("\t");            current = current.next;            count++;        } while (current != head && count <= length);        return sb.toString();    }