Leetcode linked list problem - 206. reverse linked list (learn linked list by one question and one article)

One 、 Title Description ： 

206. Reverse a linked list

Here's the head node of the list  head , Please reverse the list , And return the inverted linked list .

 

  

Two 、 Code  

//  Double pointer 
class Solution {
    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;
    }
}

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 .

This list starts with 2, The termination node is 7, Each node is distributed in different address spaces of memory , Connected in series by a pointer . 

 

Delete node ：

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

Add a node ： 

 

Compare with array ：