⭐ Introduction ⭐ ️
Hello, I'm Zhijie. I believe you all know the importance of data structure and algorithm. Among them, the linked list is the top priority. Many brothers feel that it is nothing more than a single linked list and a double linked list. It is very simple to add, delete, change and query. Indeed, although the linked list is simple, many brothers have only completed these basic functions of the linked list on their own compiler. So how to test your linked list level—— Here I have arranged a set of linked list topics for you. The topics range from simple to difficult, including all the types of linked list questions, to help you make a perfect transition. Among them, I also attached my own detailed problem solution. I brush it according to this set of problems. I believe you are more comfortable with the operation of linked list. It is recommended to collect. You can train according to the topic sequence when you are free.

📒 Blog home page: Persistent blog

🎉 Welcome to pay attention 🔎 give the thumbs-up 👍 Collection ⭐ Leave a message 📝

❤️ : Love Java learning and look forward to communicating together!

🙏 The author's level is very limited. If you find an error, please let me know. Thank you!

🌺 If you have questions, you can communicate by private letter!!!         ·

⭐ Table of contents ⭐ ️

🍋 1. Instructions and necessary abilities

🍇 2. Brush questions in order and step by step

             🌿 1. Remove linked list elements (simple)

        🌿 2. Design linked list (medium)

        🌿 3. Reverse linked list (simple but important)

        🌿 4. Switch the nodes in the linked list in pairs (medium)

        🌿 5. Delete the penultimate node in the linked list (medium)

        🌿 6. Linked list intersection (interview question)

        🌿 7. Circular linked list (simple)

                 🌿 8. Circular linked list | (medium)

🎨 3. Special summary of linked list

🍋 1. Instructions and necessary abilities

First of all, this set of topics is suggested to carry out self-examination and training to the extent that everyone has a certain understanding and mastery of the linked list. It is not suitable for Xiaobai who doesn't know the linked list. If Xiaobai still knows the linked list, it is recommended to collect the articles and read them in the future. At the same time, it is recommended to watch my linked list articles:

Single linked list learning—— Single linked list

Double linked list learning—— Double linked list

If you have the conditions to do the title of the linked list, you must demonstrate the process on the draft paper. Don't imagine it out of thin air. This is a big taboo!!!

🍇 2. Brush questions in order and step by step

        🌿 1. Remove linked list elements (simple)

Give you a head node of the linked list and an integer val. please delete all nodes in the linked list that meet the requirements Val = = Val's node and returns a new header node.

Title Link: Remove linked list elements

This question is quite basic. In order to help you get started, I spoke it in detail. All three methods are expected to be handwritten and understood.       

Method 1: the definition of linked list itself has recursive nature, which can be solved by recursive method.

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //Recursive exit
        if (head == null) {
            return head;
        }
        //Recursive call
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }
}

Methods 2 and 3: when deleting, we need to consider whether the head node is the node we need to delete, because the steps of deleting the head node are different from those of the following nodes. At this time, we can set a virtual head node in front of the real head node, so that we can uniformly complete the deletion steps of all nodes. Of course, we can also delete the head node separately. Here I have written both codes for your reference.        

//Method with virtual head node
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head==null) return head;
        //Set the virtual head node a, and next connect to the real head node
        ListNode a=new ListNode(-1,head);
        //b node is used to traverse the linked list
        ListNode b=a;
        while(b.next!=null){
            if(b.next.val==val){
                b.next=b.next.next;
            }else{
                b=b.next;
            }
        }
        //Note that you have to write a.next here, not head
        return a.next;
    }
}

//No virtual head node
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //After deleting the head node with the same value, the new head node may also have the same value, which is solved by loop
        while(head!=null&&head.val==val){
            head=head.next;
        }
        if(head==null)
            return head;
        ListNode prev=head;
        //Ensure that there are nodes after the current node
        while(prev.next!=null){
            if(prev.next.val==val){
                prev.next=prev.next.next;
            }else{
                prev=prev.next;
            }
        }
        return head;
    }
}

        🌿 2. Design linked list (medium)

Design the implementation of linked list. You can choose to use single linked list or double linked list. A node in a single linked list should have two attributes: val and next. val is the value of the current node, and next is the pointer / reference to the next node. If you want to use a two-way linked list, you also need an attribute prev to indicate the previous node in the linked list. It is assumed that all nodes in the linked list are 0-index.

Title Link: Design linked list

This problem can well test our ability to master the linked list. It requires us to realize the specified functions. We must complete it.         

class MyLinkedList {
    //Virtual head node
    Node head;
    //Used to record the number of elements
    int N;

    class Node{
        int val;
        Node next;
        public Node(){}
        public Node(int val){
            this.val=val;
        }
    }

    //Construction method
    public MyLinkedList() {
        this.head=new Node(0);
        this.N=0;
    }
    
    //Gets the value of the index node
    public int get(int index) {
        //If index is illegal, - 1 is returned
        if (index < 0 || index >= N) {
            return -1;
        }
        Node currentNode = head;
        //Contains a virtual header node, so find the index+1 node
        for (int i = 0; i <= index; i++) {
            currentNode = currentNode.next;
        }
        return currentNode.val;
    }
    
    //Insert a node at the front of the linked list
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
     //Insert a node at the end of the linked list
    public void addAtTail(int val) {
        addAtIndex(N, val);
    }

    //Complete formulation insert
    public void addAtIndex(int index, int val) {
        //Illegal direct return
        if(index>N){
            return;
        }
        //The case of index < 0 is the same as that equal to 0
        if(index<0){
            index=0;
        }
        Node curr=head;
        //Find the previous node at the location to be inserted
        for(int i=0;i<index;i++){
            curr=curr.next;
        }
        //Complete the insert operation
        Node newNode=new Node(val);
        newNode.next=curr.next;
        curr.next=newNode;
        N++;
    }
    
    public void deleteAtIndex(int index) {
        //Illegal index direct return
        if(index<0||index>=N) return;
        Node pre=head;
        //Find the previous node to insert
        for(int i=0;i<index;i++){
            pre=pre.next;
        }
        pre.next=pre.next.next;
        N--;
    } 
}

        🌿 3. Reverse linked list (simple but important)

Give you the head node of the single linked list. Please reverse the linked list and return the reversed linked list.

Title Link: Reverse linked list 

Very classic questions, interview often test, everyone must know the questions!!         

Method 1 double pointer iteration: through two pointers cur and pre, local inversion is performed once at a time, and all inversion is completed after traversing once.      

class Solution {
    public ListNode reverseList(ListNode head) {
        //cur is on the left and pre is on the right 
        ListNode pre=head;
        ListNode cur=null;
        while(pre!=null){
            //Save the next of pre first
            ListNode a=pre.next;
            pre.next=cur;
            cur=pre;
            pre=a;
        }
        return cur;
    }    
}

Method 2 recursion: the recursion of this problem is quite abstract. You need to demonstrate the process yourself to understand it, but the logic is the same as double pointer. It is recommended to master the double pointer method.

class Solution {
    public ListNode reverseList(ListNode head) {
        //Recursive exit
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

        🌿 4. Switch the nodes in the linked list in pairs (medium)

Give you a linked list, exchange the adjacent nodes, and return the head node of the linked list after exchange. You must complete this problem without modifying the value inside the node (that is, you can only exchange nodes).

Title Link: Exchange the nodes in the linked list

The idea of this problem is very similar to the above. It is through the idea of pointer. You must draw a picture. If you don't draw a picture, you will be confused. You can feel it by looking at the code in the while loop. It is confirmed again. You must draw a picture to find out the execution process for a linked list problem.

cur is set as the virtual head node. In order to operate uniformly, we must form the habit of setting virtual head nodes.

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null) return head;
        //Set a virtual header node
        ListNode dummyHead=new ListNode(-1,head);
        ListNode cur=dummyHead;
        while(cur.next!=null&&cur.next.next!=null){
            ListNode a=cur.next;
            ListNode b=cur.next.next.next;
            cur.next=cur.next.next;
            cur.next.next=a;
            cur.next.next.next=b;
            cur=cur.next.next;
        }
        return dummyHead.next;
    }   
}

Method 2 recursion:

I didn't understand recursion at first, but I found a good blog about recursion—— Recursive Teaching

class Solution {
    public ListNode swapPairs(ListNode head) {
      	//Termination condition: there is only one node left in the linked list or there is no node, so there is no need to exchange. The returned is the processed linked list
        if(head == null || head.next == null){
            return head;
        }
      	//There are three nodes in total: head, next, swap pairs (next. Next)
      	//The following task is to exchange the first two of the three nodes
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
      	//According to the second step: the linked list part that has been processed after the exchange has been completed is returned to the upper level
        return next;
    }
}

        🌿 5. Delete the penultimate node in the linked list (medium)

Give you a linked list, delete the penultimate node of the linked list, and return the head node of the linked list.

Title Link: Delete the penultimate node in the linked list

It is also a very classic topic, and there are many solutions. The most basic and important thing is to use fast and slow double pointers and virtual head nodes. We must practice repeatedly, look at the problem solution in the problem solution area, and use other people's knowledge for ourselves.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //Fast and slow pointer method
        //Define virtual header node
        ListNode dummyHead=new ListNode(-1,head);
        //Define the fast and slow pointer. The slow pointer is responsible for finding the previous node of the node to be deleted
        ListNode show=dummyHead;
        ListNode fast=dummyHead;
        //Let fast go n+1 first. When fast is finished, show just points to the penultimate n+1
        for(int i=1;i<=n+1;i++){
            fast=fast.next;
        }
        while(fast!=null){
            fast=fast.next;
            show=show.next;
        }
        //Delete the next node pointed to by show
        show.next=show.next.next;
        return dummyHead.next;
    }
}

        🌿 6. Linked list intersection (interview question)

Here are the head nodes of the two single linked lists, headA and headB. Please find and return the starting node where the two single linked lists intersect. If two linked lists have no intersection, null is returned.

Title Link: Linked list intersection

This problem is judged as a simple problem in LeetCode, but it is a little difficult. There are many small details that are easy to be ignored. For example, when judging equality, we should judge that the nodes are equal rather than the val of nodes. Here, through the length difference, the two linked lists with different lengths can be traversed from the same length when the ends are aligned. If they are equal, they can be returned directly. After traversal, they still cannot be found and return null.         

Method 1: find the starting point of the length difference system to traverse the judgment.

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
           //Calculate the length difference for judgment
           int countA=0;
           int countB=0;
           ListNode a=headA;
           ListNode b=headB;
           //Find the length of a linked list
           while(a!=null){
               countA++;
               a=a.next;
           }
           //Find the length of b linked list
           while(b!=null){
               countB++;
               b=b.next;
           }
           //Reset a, b
           a=headA;
           b=headB;
           //If B is longer, exchange them
           if(countB>countA){
               int temlen=countA;
               countA=countB;
               countB=temlen;
               ListNode temNode=a;
               a=b;
               b=temNode;
           }
           //Length difference
           int x=countA-countB;
           //Let a and b run together (end aligned)
           while(x-->0){
               a=a.next;
           }
           //Traverse a and b at the same time, and return if the same is encountered
           while(a!=null){
               //It's a==b, not a.var==b.var
               if(a==b) return a;
               a=a.next;
               b=b.next;
           }
           //Return Null not found
           return null;
    }
}

Method 2: we know that the lengths of A and B linked lists may be different, but the lengths of A+B and B+A linked lists are equal. If the ends of A and B have the same node, then A+B and B+A will have the same node, so we can overcome the difficulty of different lengths.

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a=headA;
        ListNode b=headB;
        //When a==b, either equality is found, or both are null after traversal at the same time (both are null, so they will not loop. Because the traversal lengths are equal, they will be null at the same time if they are not found at the end)
        while(a!=b){
            //If A traverses, then B
            a=a!=null?a.next:headB;
            //If B is traversed, then A is traversed
            b=b!=null?b.next:headA;
        }
        //Either a or b here is OK. When both are null, it means that there is no same node, otherwise the same node is found
        return a;
    }
}

        🌿 7. Circular linked list (simple)

Give you a head node of the linked list to judge whether there are links in the linked list.

If there is a node in the linked list that can be reached again by continuously tracking the next pointer, there is a ring in the linked list. In order to represent the rings in a given linked list, the evaluation system uses the integer pos to represent the position where the tail of the linked list is connected to the linked list (the index starts from 0). If pos is - 1, there are no rings in the linked list. Note: pos is not passed as a parameter, but only to identify the actual situation of the linked list.

Returns true if there are links in the linked list. Otherwise, false is returned.

Title Link: Circular linked list        

Method 1: use HashSet to store the traversed nodes. If it is judged that the nodes have been stored, it will directly return true. After traversal, it will return false (time complexity O (N), space complexity O (N))

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set=new HashSet<ListNode>();
        ListNode a=head;
        while(a!=null){
            if(!set.contains(a)){
                set.add(a);
            }else{
                //It shows that we have returned to the starting point of the ring, there is a ring
                return true;
            }
            a=a.next;
        }
        //After traversing, there is no duplicate node and no ring
        return false;
    }
}

Method 2 tortoise and rabbit race: in fact, it is also a fast and slow double pointer method. If the linked list becomes a ring, the fast pointer will catch up with the slow pointer because it is faster than the slow pointer, so it will exceed the slow pointer by one circle. If the fast pointer runs to the end point and is close to null, it means that the linked list is acyclic.

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null) return false;
        //The fast pointer needs to be on the right of the slow pointer to enter the following while loop body
        ListNode slow=head;
        ListNode fast=head.next;
        while(slow!=fast){
            //If fast is about to be null, it means that false is returned at the end of the linked list, and the linked list has no ring
             if(fast==null||fast.next==null) return false;
             fast=fast.next.next;
             slow=slow.next;           
        }
        //Jump out of the loop, indicating slow==fast, the fast pointer catches up with the slow pointer, and the linked list has a ring
        return true;
    }
}

        🌿 8. Circular linked list | (medium)

Given a linked list, return the first node from the linked list into the ring. If the linked list is acyclic, null is returned.

If there is a node in the linked list that can be reached again by continuously tracking the next pointer, there is a ring in the linked list. In order to represent the rings in a given linked list, the evaluation system uses the integer pos to represent the position where the tail of the linked list is connected to the linked list (the index starts from 0). If pos is - 1, there are no rings in the linked list. Note: pos is not passed as a parameter, but only to identify the actual situation of the linked list.

Modification of linked list is not allowed.

Title Link: Circular linked list||

It is different from the type of the previous question, but the return value is different, so most methods are general.         

Method 1: similarly to method 1 of the previous question, use HashSet to traverse, find the stored node is the starting point of the ring, and return directly.

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set=new HashSet<ListNode>();
        ListNode a=head;
        while(a!=null){
            if(!set.contains(a)){
                set.add(a);
            }else{
                //It has been stored, indicating that this is the starting point of the ring
                return a;
            }
            a=a.next;
        }
        //The traversal ends, indicating that there is no loop
        return null;
    }
}

Method 2 double pointer: similar to the double pointer idea of the previous problem, but this problem will be a little difficult and needs some mathematical induction and proof. Similarly, after the first time the fast and slow pointers meet, it can be judged that there is a ring. At this time, reset the fast pointer to the head, and then walk one grid at a time like the slow pointer. When they meet again, they will be at the entrance of the ring. Here is a link to a proof of mathematical induction: Double finger needling

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null) return null;
        ListNode slow=head;
        ListNode fast=head;
        while(true){
            //Description acyclic directly returns null
            if(fast==null||fast.next==null) return null;
            fast=fast.next.next;
            slow=slow.next;
            //First meeting
            if(slow==fast) break;
        }
        fast=head;
        while(fast!=slow){
            slow=slow.next;
            fast=fast.next;
        }
        return fast;
    }
}

🎨 3. Special summary of linked list

In fact, we can easily sum up some routines and skills through the above questions. 1. Set virtual header node. Because the processing of header nodes in the linked list is often special, setting virtual header nodes can help us operate uniformly. 2. Manual iterative process. The most taboo for linked list topics is to rely on your brain to imagine out of thin air. Especially in the beginner stage, you can demonstrate the process yourself in order to write logically clear code. 3. Multi collocation double pointer algorithm. Through the above special training, it is easy to see that the proportion of linked list and double pointer matching is very large, so you can often consider whether the double pointer algorithm is feasible when doing questions. 4. Train repeatedly and practice more. This is also the most important. You can train this set of questions repeatedly to deepen your impression, and look for more linked list questions for training at the same time. I believe that with this set of topics, I will be able to tear the code in the future interview!

If you feel useful brothers, please support it for three times!!! thank

Surprise at the end of the article:

                

Java learning route summary, brick movers counter attack Java Architects