Leetcode linked list problem -- 24. Exchange the nodes in the linked list in pairs (learn the linked list with one question and one article)

One 、 Title Description ： 

24. Two or two exchange nodes in a linked list

Medium difficulty 1478 Switch to English to receive dynamic feedback

I'll give you a list , Two or two 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 （ namely , Only node switching can be performed ）.

 

  

Two 、 Code  

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

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 ：