Leetcode linked list problem - 203. remove the linked list elements (learn the linked list by one question and one article)

One 、 Title Description ： 

203. Remove linked list elements

Give you a list of the head node  head  And an integer  val , Please delete all the contents in the linked list  Node.val == val  The node of , And back to   New head node  .

  

Two 、 Code  

public ListNode removeElements(ListNode head, int val) {
    if (head == null) {
        return head;
    }
    //  Because the deletion may involve the head node , So set dummy node , Unified operation 
    ListNode dummy = new ListNode(-1, head);
    ListNode pre = dummy;
    ListNode cur = head;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return dummy.next;
}

3、 ... and 、 Understand 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 ：

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 .

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 linked list links the nodes in the memory through the pointer of the pointer field .

So the nodes in the linked list are not continuously distributed in memory , It's scattered on some address in memory , The allocation mechanism depends on the memory management of the operating system .

Delete node ：

As long as C Node next The pointer Point to E Node is OK .

Add a node ： 

 

Compare with array ：