Leetcode featured 200 -- linked list

Preface

Learning data structures is best done with C The basis of language , Did you learn C It will be easy to learn data structure after learning the pointer of language

Recommended books ：CPrimerPlus、 Big talk data structure

resources

Brush question website

Random code recording (programmercarl.com)

Drawing software

OneNote

Note taking software

Typoral

Theoretical basis of linked list

Type of linked list

What is a linked list , A linked list is a linear structure connected in series by pointers , Each node consists of two parts , One is the data field and the other is the pointer field （ Holds a pointer to the next node ）, The pointer field of the last node points to null（ A null pointer means ）.

The entry node of the link is called the head node of the linked list head.

Single chain list

The above form is a single linked list

Double linked list

A node in a single linked list can only point to the next node of a node .

Double linked list ： Each node has two pointer fields , One points to the next node , One points to the previous node .

Double linked list You can query forward or backward .

As shown in the figure ：

Circular linked list

Circular linked list , seeing the name of a thing one thinks of its function , The linked list is connected end to end .

Circular list can be used to solve the Joseph Ring problem .

How to store linked lists

Arrays are continuously distributed in memory , But linked lists are not continuously distributed in memory . The allocation mechanism depends on the memory management of the operating system .

Definition of linked list

This is C/C++ The definition of

//  Single chain list 
struct ListNode {
    
    int val;  //  Elements stored on nodes 
    ListNode *next;  //  Pointer to the next node 
    ListNode(int x) : val(x), next(NULL) {
    }  //  Node constructors 
};

We are Java How to define ？

In fact, they are all similar , We simulate one object by one , First we need to define a class , This is the template of the object

package com.sequenceTable.linkedlist1;

public class ListNode {
    
    public int val; //  Elements stored on nodes 
    public ListNode next; // Point to next node 

    public ListNode() {
    
    }

    public ListNode(int val) {
    
        this.val = val;
    }


    @Override
    public String toString() {
    
        return "ListNode{" +
                "val=" + val +
                '}';
    }
}

Delete node

Delete node D, It's very simple, as shown in the figure , Point the original to D Pointer to node ( References to objects ) Point to E Nodes can be deleted D The node ~

Java Garbage collection mechanism in ,D Nodes that are not referenced will be recycled

Add a node

It can be seen that the addition and deletion of linked list are $O(1)$ operation , And it doesn't affect other nodes .

But be careful , If you delete the fifth node , You need to find the fourth node from the beginning through next Pointer to delete , The time complexity of the search is $O(n)$.

Comparison of linked list and data characteristics

When an array is defined , The length is fixed , If you want to change the length of the array , You need to redefine a new array .

The length of the linked list can be unfixed , And it can be added and deleted dynamically , Suitable for data volume is not fixed , Add and delete frequently , Less query scenarios .

Remove linked list elements

The question ： Delete the given value in the list val My place With nodes .

Example 1：
Input ：head = [1,2,6,3,4,5,6], val = 6
Output ：[1,2,3,4,5]

Example 2：
Input ：head = [], val = 1
Output ：[]

Example 3：
Input ：head = [7,7,7,7], val = 7
Output ：[]

Ideas

If you use C,C++ Programming language , Don't forget to delete these two removed nodes from memory

Of course if you use java ,python You don't have to manually manage memory .

Two ways of linked list operation ：

• Directly use the original linked list to delete the operation .
• Set a virtual head node to delete .

Look at the first operation ： Use the original linked list directly to remove .

Removing the head node is not the same as removing other nodes , Because other nodes in the linked list remove the current node through the previous node , And the head node has no previous node .

So how to remove the head node , In fact, just move the head node back one bit , This removes a header from the list .

Then delete it in memory

This removes a header node , Did you find out , Remove the head node from the list and The operation of removing other nodes is different , In fact, when you write code, you will find that , You need to write a separate piece of logic to deal with the removal of the head node .

Then can we Remove with a unified logic What about the nodes of the linked list .

Actually You can set up a virtual head node , In this way, all nodes in the original linked list can be removed in a unified way .

Let's see how to set up a virtual head . Still in this list , Remove elements 1.

Here we add a virtual head node to the linked list as a new head node , At this point, remove the old header element 1.

In this way, we can use and remove other nodes in the linked list in a unified way ？

Take a look at , How to remove elements 1 Well , Or the familiar way , Then delete the element from memory 1.

Finally, in the title ,return At the head node , Don't forget return dummyNode->next;, This is the new head node

In fact, when you think about this problem, you can think of an iterative way , Keep looking back , Change the direction after finding , No, continue to move back , Just pay attention to one special case , That is, when the target value is the head node , So we define a virtual node directly . This will match the situation

java The code is as follows ：

package com.sequenceTable.linkedlist1;

public class removelinkedlistelements {
    
    public ListNode removeElements(ListNode head,int val){
    
        //  Because the deletion may involve the head node , So set dummy node , Unified operation 
        //dummy It means virtual 
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prev = dummy;

        // Judge whether the successor node of the current node is null
        while (prev.next != null){
    
            // If the value of the current node and subsequent nodes is different from the given val equal 
            // You need to delete its subsequent nodes 
            if (prev.next.val == val){
    
                prev.next = prev.next.next;
            }else {
    
                //  If the value of the subsequent node of the current node is not equal to the given value 
                //  Then the current node needs to be reserved , therefore prev Move forward one position 
                prev = prev.next;
            }
        }
//  Finally, the head node after deletion is returned 
        return dummy.next;
    }
}

Design the list

Ideas

This chapter ,java It's not easy to understand

If there is no foundation , First look at C-PrimerPlus And big talk data structure

Finally, I recommend the data structure and algorithm course of shangsilicon Valley , It must be this order ！

There is no turning place , Is that you are familiar with the linked list , know CRUD How the pointer changes can be written

Implement these functions in the linked list class ：

get(index)： Get the index Values of nodes . If the index is invalid , Then return to -1.

addAtHead(val)： Add a value of... Before the first element of the list val The node of . After inserting , The new node will be the first node in the list .

addAtTail(val)： Will be worth val To the last element of the list .

addAtIndex(index,val)： In the list, the index The value added before nodes is val The node of . If index It's equal to the length of the list , Then the node will be attached to the end of the list . If index Greater than the length of the list , The node will not be inserted . If index Less than 0, Then insert the node in the head .

deleteAtIndex(index)： If the index index It works , Delete the index Nodes .

The change of delete node pointer is as follows ：

Add the following changes to the linked list node pointer ：

package com.caq.linkList;

public class MyLinkedList {
    
    int size;
    ListNode head;
    // Initialize linked list 
    public MyLinkedList() {
    
        size = 0;
        head = new ListNode(0);
    }

    // For the first index The number of nodes 
    public int get(int index) {
    
        // If index illegal , return -1
        if (index < 0 || index >= size) {
    
            return -1;
        }
        ListNode currentNode = head;
        // Contains a virtual header node , So find number one  index+1  Nodes 
        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(size, val);
    }

    //  In the  index  Insert a new node before two nodes , for example index by 0, Then the newly inserted node is the new head node of the linked list .
    //  If  index  It's equal to the length of the list , The newly inserted node is the tail node of the linked list 
    //  If  index  Greater than the length of the list , It returns null 
    public void addAtIndex(int index, int val) {
    
        if (index > size) {
    
            return;
        }
        if (index < 0) {
    
            index = 0;
        }
        size++;
        // Find the precursor to insert the node 
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
    
            pred = pred.next;
        }
        ListNode toAdd = new ListNode(val);
        toAdd.next = pred.next;
        pred.next = toAdd;
    }

    // Delete the first index Nodes 
    public void deleteAtIndex(int index) {
    
        if (index < 0 || index >= size) {
    
            return;
        }
        size--;
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
    
            pred = pred.next;
        }
        pred.next = pred.next.next;
    }
}

Reverse a linked list

Ideas

Change linked list next Pointer pointing , Reverse the list directly

This animation is excellent, okay , It's really easy to see what it means ！！！

So let's define a cur The pointer , Point to the head node , Let me define one more pre The pointer , Initialize to null.

And then it's going to start reversing , First of all, put cur->next For nodes tmp Save the pointer , That is to save this node .

Why save this node , Because the next thing to change cur->next Of points to , take cur->next Point to pre , The first node has been reversed .

Next , It's the following code logic , Keep moving pre and cur The pointer .

Last ,cur The pointer has pointed to null, The loop ends , The list has been reversed . At this point we return pre Just a pointer ,pre The pointer points to the new header

The initial situation is shown in the figure below ：

package com.caq.linkList;

public class SolutionReverseList {
    
    public ListNode reverseList(ListNode head) {
    
        ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null) {
    
            temp = cur.next;//  Save the next node 
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
}

temp = cur.next

The meaning here is to cur.next Point to temp, Also is to temp Point to the second node

The function is to reverse the order

Recursive method

Similar to double pointer

public ListNode reverseList(ListNode head) {
    
    return reverse(null, head);
}

private ListNode reverse(ListNode prev, ListNode cur) {
    
    if (cur == null) {
    
        return prev;
    }
    ListNode temp = null;
    temp = cur.next;//  Save the next node first 
    cur.next = prev;//  reverse 
    //  to update prev、cur Location 
    // prev = cur;
    // cur = temp;
    return reverse(cur, temp);
}

Two or two exchange nodes in a linked list

Given a linked list , Two or two exchange the adjacent nodes , And return the list after exchange .

You can't just change the values inside the node , It needs to actually exchange nodes .

Ideas

This topic can be simulated normally .

Next is to exchange two adjacent elements , At this time, we must draw pictures , No drawing , It's easy to mess with multiple pointers , And the order of operation

At the beginning ,cur Point to the virtual header node , Then proceed to the following three steps ：

Be sure to draw this process by yourself

recursive

public ListNode swapPairs(ListNode head) {
    
    // base case  Exit submission 
    if(head == null || head.next == null) return head;
    //  Get the next node of the current node 
    ListNode next = head.next;
    //  Recursion 
    ListNode newNode = swapPairs(next.next);
    //  Exchange here 
    next.next = head;
    head.next = newNode;

    return next;
}

The process of recursion is as follows ：

Virtual header node

public ListNode swapPairs(ListNode head) {
    

    ListNode dummyNode = new ListNode(0);
    dummyNode.next = head;
    ListNode prev = dummyNode;

    while (prev.next != null && prev.next.next != null) {
    
      ListNode temp = head.next.next; //  cache  next
      prev.next = head.next;          //  take  prev  Of  next  Change it to  head  Of  next
      head.next.next = head;          //  take  head.next(prev.next)  Of next, Point to  head
      head.next = temp;               //  take head  Of  next  Connect the cached temp
      prev = head;                    //  Stepping 1 position 
      head = head.next;               //  Stepping 1 position 
    }
    return dummyNode.next;
  }

Delete the last of the linked list N Nodes

Ideas

The classic application of double pointer , If you want to delete the penultimate n Nodes , Give Way fast Move n Step , And then let fast and slow Move at the same time , until fast Point to the end of the list . Delete slow The node you point to is OK .

The illustration

1、 The initial conditions

2、fast First of all, let's go n + 1 Step , Why n+1 Well , Because that's the only way to move at the same time slow To point to the previous node of the deleted node （ Easy to delete ）, Pictured ：

3、fast and slow Move at the same time , until fast Point to the end

4、 Delete slow Point to the next node

I really can't think of this , First write down the familiar ideas ！

public ListNode removeNthFromEnd(ListNode head, int n) {
    
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode slow = dummy;
        ListNode fast = dummy;
        while (n-- > 0) {
    
            fast = fast.next;
        }
        //  remember   Node to be deleted slow  Last node of 
        ListNode prev = null;
        while (fast != null) {
    
            prev = slow;
            slow = slow.next;
            fast = fast.next;
        }
        //  Of the previous node next Pointer bypass   Node to be deleted slow  Direct to slow The next node of 
        prev.next = slow.next;

        return dummy.next;
    }	

The list intersects

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

Ideas

Simply speaking , Is to find the intersection node of two linked lists The pointer , The intersection is not equal in value , Instead, the pointers are equal .

For the convenience of example , Assume that the values of node elements are equal , Then the node pointers are equal .

We find the length of the two linked lists , And find the difference between the lengths of the two linked lists , And then let curA Move to , and curB End aligned position , Pictured ：

At this point, we can compare curA and curB Are they the same? , If it's not the same , Move back at the same time curA and curB, If you encounter curA == curB, Then find the intersection .

Otherwise, the loop exits and returns a null pointer .

public class LinkedListCrossing {
    
    public ListNode getNewLinkedListCrossing(ListNode headA, ListNode headB){
    
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0, lenB = 0;

        while (curA != null){
    
            lenA++;
            curA = curA.next;
        }

        while (curB != null) {
     //  Find the linked list B The length of 
            lenB++;
            curB = curB.next;
        }

        curA = headA;
        curB = headB;

        //  Give Way curA For the head of the longest linked list ,lenA Is its length 
        if (lenB > lenA) {
    
            //1. swap (lenA, lenB);
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            //2. swap (curA, curB);
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        //  Length difference 
        int gap = lenA - lenB;
        //  Give Way curA and curB At the same starting point （ End position alignment ）
        while (gap-- > 0) {
    
            curA = curA.next;
        }
        //  Traverse curA  and  curB, If you encounter the same, you will directly return 
        while (curA != null) {
    
            if (curA == curB) {
    
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;

    }
}

curA = headA;curB = headB;

Because the previous code traverses through pointers , Get linked list length calculation lenA,lenB

Then write this line of code, which means to return the pointer to the original position

Other things you don't understand , Code comments are marked

Circular list

The question ： Given a linked list , Return to the first node of the link where the list begins to enter . If the list has no links , Then return to null.

To represent a ring in a given list , Use integers pos To indicate where the end of the list is connected to the list （ Index from 0 Start ）. If pos yes -1, There are no links in the list .

explain ： It is not allowed to modify the given linked list .

Topic meaning

What does the title mean , In fact, you can understand with a few more examples

If it is a unidirectional linked list with multiple nodes , Is the same , The entry point is the second node

If the linked list is like this , Then the entry point is the fourth node

Ideas

There are only two steps to complete this problem

• Determine if the list has links
• Find the entrance to this ring

Determine if the list has links

fast The pointer must enter the ring first , If fast Pointers and slow If the pointer meets , Must have met in the ring , There is no doubt that .

Find the entrance to this ring

public class Solution {
    
    public ListNode detectCycle(ListNode head) {
    
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
    
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
    //  Ring 
                ListNode index1 = fast;
                ListNode index2 = head;
                //  Two pointers , Ab initio node and encounter node , Take one step each , Until we met , The meeting point is the ring entrance 
                while (index1 != index2) {
    
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}

summary

• The main types of linked lists are ： Single chain list , Double linked list , Circular linked list
• How to store linked lists ： The nodes of the linked list are stored separately in memory , Connected by a pointer .