The introduction

A linked list is a chain storage structure stored by nodes. A node contains a data domain (storing data) and a next domain (storing Pointers of the next node). The nodes of the linked list are not necessarily continuous, but can be divided into leading nodes and non-leading nodes. The header contains only the next field.

If you are not familiar with linked lists, I suggest you take a look at one of my articles. In this article, we will focus on the use of linked list tips, how to use these tips to solve problems, in-depth analysis of LeetCode’s representative linked list problems, trust me, after reading this article, you will never have to worry about linked list problems.

1. Explain several concepts of linked lists

In fact, the structure of the linked list is relatively simple, and the obstacles to our understanding of the linked list are often due to the pointer of the list, boundary problems, etc., which sometimes make us very upset, do not panic, we will follow a pair of this concept analysis, I believe you will have a harvest.

1.1 What are Pointers in a linked list

When we studied C, we learned about Pointers, which describe pointing to a memory address, and in Java, we don’t have Pointers, but we can think of them as references.

When we assign a variable (object) to a pointer (reference), we are actually assigning the address of the variable (object) to the pointer (reference).

P - > next = q;// Indicates that the subsequent pointer to the p node stores the memory address of the Q node.P - > next = p - > next - > next;// The next pointer to p stores the memory address of the next node of p.
Copy the code

1.1 Where does the pointer Point

When we write linked list code, we use Pointers that point back and forward, which quickly confuse us, and it’s easy to lose Pointers and leak memory. Let’s generalize these two concepts:

Pointer missing: a pointer that you have defined is missing.

Memory leak: A node in a linked list that has no definite pointer determination throws a null pointer exception at runtime.

We analyze the specifics of pointer loss and memory leak by inserting and deleting nodes

  • Insert the node

Insert node X between node A and node B, where B is the next node of A and p points to node A.

P - > next = x; X - > next = p - > next;Copy the code

Such code causes pointer loss and memory leaks, because it causes the successor pointer to the X node to point to itself.

The correct code should be:

X - > next = p - > next; P - > next = x;Copy the code

  • Remove nodes

Similarly, delete node B between node A and node C, where b is the next node of A and p points to node A. The correct code should be:

P - > next = p - > next - > next;Copy the code

When deleting a node, we usually add sentinels (head nodes) to the head of the linked list, considering that the deleted node may be the first node in the list. In this way, the code for deleting the linked list is consistent, and there is no need to consider whether it is the first node.

The code for adding a sentinel to the list is:

 // Define a sentinel as the head of the incoming list
 ListNode pre =new ListNode(0);
 pre.next=head;
Copy the code

1.3 Judge boundary conditions

When dealing with linked lists, the boundary judgment conditions of linked lists should be fully considered. Under normal circumstances, we often use the following judgment conditions:

  • Does the code work if the list is empty?

  • Does the code work if the linked list contains only one node?

  • Does the code work if the linked list contains only two nodes?

  • Does the code logic work when dealing with heads and tails?

These judgment criteria need to be used in conjunction with their own actual scenarios

2, must master several kinds of topics

In the above study, we have analyzed some error-prone concepts of linked lists. Now, let’s talk about real code practice. When I brush questions on LeetCode, I find that linked lists are usually divided into the following categories:

  • Inversion of single linked lists (LeetCode206)
  • Detection of Linked List Rings (LeetCode141)
  • The Combination of two ordered lists (LeetCode21)
  • Delete linked lists (LeetCode18)
  • Delete the NTH node from the penultimate list (LeetCode19)
  • Find intermediate node of linked list (LeetCode876)

These kinds of linked list questions basically cover most of the knowledge points, in the following study, we will conquer it one by one, I believe that after mastering them, in the future written test/interview, more can follow one’s inclinations.6.

2.1 Single-Linked List Inversion (LeetCode206)

Change the address in next to the address of the previous node, but to prevent the loss of the list, create a pointer to the next node before each change.

class Solution {
    public ListNode reverseList(ListNode head) {

if(head==null||head.next==null) {return head;
}
    ListNode p1=head;
      // Use a new list
    ListNode p2=null;
    while(p1! =null) {// Save the next node before changing the pointer
        ListNode temp=p1.next;
        p1.next=p2;
        p2=p1;
        p1=temp;
    }
    returnp2; }}Copy the code

2.2 Detection of ring in linked List (LeetCode141)

We define two Pointers, p1 and p2, where p1 takes one step at a time and P2 takes two steps at a time. If there is a loop in the list, then p1==p2 must at some point be satisfied

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null) {return false;
        }
        ListNode slow=head;
        ListNode fast=head.next;
       while(fast! =null&&fast.next! =null) {if(slow==fast){
                return true;
            }
            slow=slow.next;
            fast=fast.next.next;
        }
        return false; }}Copy the code

NOTE: For fast Pointers, if you want to use fast Pointers as a judgment condition, both fast and fast.next need to check whether they are null. (Not across levels)

2.3 Merge two Ordered Linked Lists (LeetCode21)

You can create a new linked list for the result of the merge

  • Neither list is empty

Define a pointer to find the appropriate node and place it next in the newly created linked list

  • One of the linked lists is empty

Place the non-empty list in the next position in the newly created list

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        if(l1==null) {return l2;
        }
        if(l2==null) {return l1;
        }
        ListNode result=new ListNode(0);
        ListNode temp=result;
        // Neither list is empty
        while(l1! =null&&l2! =null) {if(l1.val<=l2.val){
                temp.next=l1;
                temp=temp.next;
                l1=l1.next;
            }
            else{ temp.next=l2; temp=temp.next; l2=l2.next; }}// One of the linked lists is empty
       if(l1==null){
           temp.next=l2;
       }
       else{
           temp.next=l1;
       }

        returnresult.next; }}Copy the code

2.4 Deleting linked Lists (LeetCode18)

You can add a sentinel to the head of the linked list. When deleting the linked list, you can find the last position of the deleted list.

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head==null) {return null;
        }
        // Define a sentinel as the head of the incoming list
        ListNode pre =new ListNode(0);
        pre.next=head;
        
        ListNode temp=pre;
        while(temp! =null) {if(temp.next.val==val){
                temp.next=temp.next.next;
                break;
            }
            else{ temp=temp.next; }}returnpre.next; }}Copy the code

2.5 Delete the NTH node from the penultimate of the linked list (LeetCode19)

Use sentries when deleting nodes.

  • Count is the length of the array
  • Locate the previous location of the node to be deleted, count-n-1
  • Remove nodes
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pre=new ListNode(0);
        pre.next=head;
        ListNode temp1=pre;
        ListNode temp2=pre;
        int count=0;
        while(temp1! =null){
            temp1=temp1.next;
            count++;
        }

        while(count-n-1>0){
            temp2=temp2.next;
            count--;
        }
        temp2.next=temp2.next.next;
        
        returnpre.next; }}Copy the code

2.6 Finding intermediate nodes of linked Lists (LeetCode876)

Count /2 = count/2 = count/2

class Solution {
    public ListNode middleNode(ListNode head) {
        if(head==null) return null;
        ListNode temp=head;
       int count=0;
       while(temp! =null){
        temp=temp.next;
        count++;
       }
       int mid=count/2;
       ListNode result=head;
       while(mid>0){
          result=result.next;
          mid--;
       }
       returnresult; }}Copy the code

Note: Practice is the only standard to test the truth, to really learn the linked list knowledge point, only learning theory is not reliable, we need to knock more code, more thinking, more writing and practice, for the abstract topic, you can draw pictures for example, to assist their own thinking.

3. Experience of learning linked lists

1. When a function needs to move the list, it is best to create a pointer to move the list, so as not to change the original pointer position.

2, a single linked list has a lead node and not a lead node linked list, generally do the default header is valuable.

3, linked list memory is discontinuous, a node occupies a block of memory, each memory has a location (next) to store the address of the next node.

3, linked list to find the idea of the ring: fast and slow pointer, create two Pointers, a fast pointer: a walk two steps, a slow pointer: a walk one step, if the encounter is a ring, if pointing to null, no ring.

Create two Pointers. The first pointer queries the number of nodes in the list count, and then count-k determines the location of the node to be deleted. The second pointer traverses the list to count-n-1.

5. Reverse linked list idea: reverse the pointer of each node from front to back, that is, change the address in next to that of the previous node, but in order to prevent the loss of the following linked list, create a pointer to the next node before each change.

conclusion

Whenever we learn any points need to be on the basis of mastering technique (use), learning (source), learning data structure and algorithm is the same, we should not only learn how to use it, more to grasp why if you use it, compared to other methods, what are the advantages of it, is it has low time complexity and space complexity is small, Or does its data structure fit the scenario, etc…

reference

[1] Wang Z. The beauty of data structures and algorithms

[2]LeetCode China website

Brush problem combination boxing recommendation

In the past 3 months, the author sorted out commonly used data structure and algorithm and Miaosajian offer. The official account replied data structure and algorithm and Miaosajian offer respectively, and you can get two sets of e-books, hoping to help you.

I am Simon Lang, a young man who wants to learn a little bit every day. Pay attention to me. Let’s advance together and learn together.