2 w word | 28 LeetCode topic show you the list of those routines

LeetCode on the list of hot topics, if you have questions, welcome to correct!

Related articles:

【 1 】 3.5 w word | 47 LeetCode topic show you those routines binary tree (on)

【 2 】 3.5 w word | 47 LeetCode topic show you binary tree those routines (below)

1. The concept of linked lists

(1) Structure of the linked list

In computers, a data structure in which each element has an address to the next element, instead of being kept in continuous storage, is called a Linked List. Each element in the list can be called a Node, while the first element in the list is called a Head Node, and the last element is called a Tail Node.

The structure of the list definition, contains two information, one is data information, used to store data, also known as the data domain; The other is address information, which stores the address of the next node, also known as the pointer field.

As you can see, the list node is an integer, where the first list node stores the data 763, and the pointer field stores the address 0x56432, which is the address of the second list node. In this way, the first node points to the second node, so the two nodes logically form a pointing relationship.

In the pointer to the second node, we store an address, which is 0x0, and that address corresponds to 0. This is a special address, we call it the NULL address, and we use NULL to indicate the empty address. The second list node points to the null address, which means it is the last node in the list structure.

In JavaScript, the definition of a linked list contains two properties, val to hold data on a node, and next to hold links to the next node. The node is created using a constructor that sets the values of these two properties:

function ListNode(val) {
     this.val = val;
     this.next = null;
 }
Copy the code

Note that there is only one next variable in the pointer field of a linked list structure, which means that each list node can only uniquely point to the next node. There is no concept of Pointers in JavaScript, so we can understand that a pointer is a reference to an address.

(2) Linked list and array comparison

In fact, the list structure is similar to the array structure, except that the array structure is stored continuously in memory. Due to the existence of the pointer field in the list structure, the location of each node in memory is not necessarily continuous. Let’s compare the performance of the two.

The size of an array cannot be changed after creation. To add elements, you must create a new array. So, sometimes in order to dynamically increment elements, you declare more space than you need at the beginning of the array, so that new elements can be added later. This is a waste of space, so the utilization of the array is equal to the size you need divided by the size of the array you created.

Since elements in a linked list are created only when needed, there is no need to reserve more space. For us, only the value in the node is available, and the memory that holds the node address is not available to us. So the spatial utilization of the list is equivalent to the size of the value divided by the sum of the size of the value and the size of the node address.

The time complexity of accessing an array element is O(1). Because of the nature of sequential access, accessing the NTH element of the list requires traversal from the first element to the NTH element, so the average time complexity is O(N).

In the case of an array, whether an insert occurs at the end of the array or in the middle of the array, the average time is O(N) because a new array needs to be created and the previous elements copied into the new array. For a linked list, if the address of the tail node is always maintained, then inserting a new element takes only O(1) time. When inserting an element into the middle of the list, the average time complexity is O(N) because of the sequential access feature of lists, which requires first traversing the list, starting from the first node to the NTH position, and then inserting again.

(3) The form of linked list

1) One-way linked listAll linked list nodes only hold information that points to the next node address. The Singly Linked List, which holds both data in one node and information pointing to the next node, is called a Singly Linked List. As shown in the figure below:

2) Two-way linked listA unidirectional linked list has the limitation that it can only be traversed in one direction, since information pointing to the address of the next node can be stored as well as information pointing to the address of the last node. This is called a two-way Linked List, which does data in a node and holds the address information of the next and last node. Just like the next node of the tail node in the linked list only holds an empty address, the address of the last node of the head node in the linked list also holds an empty address, as shown in the figure below:

(3) Circular linked listWhether it is a unidirectional Linked List or a bidirectional Linked List, when traversing to the tail node, it cannot be traversed again. If the tail node points to the address of the next node and the information is updated to point to the head node, the whole Linked List forms a loop. This kind of Linked List is called Circular Linked List. As shown in the figure below:

2. Operation of the linked list

Dummy Head – a Dummy Head – is a Dummy Head. In fact, you put an extra node in front of the list. In this case, there are N+1 nodes in the list with the false head, which holds N data.

That extra node won’t hold any meaningful data. So what does it do?

In fact, after adding false head, can omit a lot of null pointer judgment, the list of various operations will become more concise. Related to the list of various operations, mainly the following six basic operations:

• The linked list is initialized
• Tail-appended node
• Header insertion node
• To find the node
• Before inserting the specified position
• Delete nodes

The following is LeetCode 707 “Design a linked list” as an example, to implement the single linked list, the topic requires the six basic operations to be implemented: the /code here/ section in the comment is filled in the corresponding six functional codes:

var MyLinkedList = function() {
   /* code here: initialize the list */
};

MyLinkedList.prototype.addAtTail = function(val) {
  /* code here: appends a node with value val to the end of the list */
};

MyLinkedList.prototype.addAtHead = function(val) {
  /* code here: insert a new node with the value val, making it the first node */
};

MyLinkedList.prototype.get = function(index) {
	/* code here: obtain the value of node index in the list. If the index is invalid, -1 */ is returned
  // Index starts from 0.
};
  
MyLinkedList.prototype.addAtIndex = function(index, val) {
	// code here:
  // Add node val before node index in the linked list.
  // 1. If index is equal to the length of the list, this node is appended to the end of the list.
  // 2. If index is greater than the length of the linked list, the node will not be inserted.
  // 3. If index is less than 0, insert before the head node
};

MyLinkedList.prototype.deleteAtIndex = function(index) {
	/* code here: if index is valid, delete node */
};
Copy the code

(1) List initialization

To initialize a dummy list, we need to create a new node and make the dummy and tail Pointers of the list point to it.

var listNode = function(val) {
    this.val = val
    this.next = null
};

var MyLinkedList = function() {
    this.dummy = new listNode()
    this.tail = this.dummy
    this.length = 0
};

Copy the code

After initialization, the list has a node, but at this point, there is no data in the list. Therefore, for an empty list, it means an already initialized list with false headers.

Although both head and tail point to null after initialization. But these two have a characteristic called “static and static combination” :

• Static: Once the head pointer is initialized, it is always static and never moves again.
• Move: The tail pointer is moved whenever the list changes.

(2) Append nodes to the tail

Adding a new node to the end is a two-step operation, as follows:

MyLinkedList.prototype.addAtTail = function(val) {
    // Add a new node to the end
    this.tail.next = new listNode(val)
    // Move the tail pointer
    this.tail = this.tail.next;
    // List length +1
    this.length ++
};
Copy the code

After initializing a list with a dummy head, the tail pointer is always guaranteed to be non-null, so you can directly modify the tail.next pointer, omits the confirmation that the tail pointer is null.

(3) Insert a node into the head

The new node that needs to be inserted is p, and after insertion, the new node P becomes the first meaningful data node. The header insertion can be done in the following 3 steps:

• The new node p.next points to dummy. Next;
• Dummy. Next points to p;
• If the original tail points to dummy, then tail points to p.

The corresponding code is as follows:

MyLinkedList.prototype.addAtHead = function(val) {
    // Generate a node with the value val
    const p = new listNode(val)
    // Point p.next to the first node
    p.next = this.dummy.next;
    Dummy. Next refers to the new node, making it the first node
    this.dummy.next = p;
    // Modify the tail pointer when adding nodes.
    if (this.tail == this.dummy) {
      this.tail = p;
    }
    // List length +1
    this.length ++
};
Copy the code

What’s interesting about this code is that it still works when the list is empty. Because even though the list is empty, the code does not encounter a null pointer because of the dummy node.

Note: If nodes are added to or removed from the list, be sure to modify the tail pointer. If you forget to modify, you will not get the trailing pointer of the list correctly, and you will incorrectly access the data in the list.

(4) Find nodes

When looking for nodes with index (assuming index starts from 0), you should note that in most cases it is more useful to return prev, which is the node in front of the specified node. The benefits are as follows:

• Prev. next is used to access the desired node. If no node is found, then prev.next is null.
• Prev makes it easy to perform subsequent operations, such as inserting a new node in front of the target or moving the target node out of the linked list.

Therefore, if we want to implement get, we should first implement getPrevNode:

MyLinkedList.prototype.getPreNode = function(index) {
    if (index < 0 || index >= this.length) {
      return -1;
    }
    // Initialize front and back, respectively
    let front = this.dummy.next
    let back = this.dummy
    // When searching, front and back always walk together
    for (let i = 0; i < index && front ! =null; i++) {
      back = front;
      front = front.next;
    }
    // Set back as prev and return
    return back
};
Copy the code

With the help of the dummy header, the lookup code is very robust and can handle the following two situations:

• If target does not exist in the list, prev returns the last node in the list.
• If prev is an empty linked list (an empty list is a list with only one dummy head), then prev points to dummy. That is, the returned prev pointer is always valid.

GetPrevNode = getPrevNode ();

MyLinkedList.prototype.get = function(index) {
    // Obtain the value of node index in the list. If the index is invalid, -1 is returned.
    // Index starts from 0
    if (index < 0 || index >= this.length) {
      return -1;
    }
    GetPrevNode always returns a valid node, so it can be used directly.
    return this.getPreNode(index).next.val
};
Copy the code

(5) Before insertion at the specified position

Before the insertion is specified, there are four requirements.

• If index is greater than the length of the list, the node will not be inserted.
• If index is equal to the length of the list, this node is appended to the end of the list.
• If index is less than 0, insert a node in the header.
• Otherwise, insert the node before the specified position.

Cases 1 to 3 are easier to handle. I could just write it. The point is Case 4. Now that we have the getPrevNode() function, we can easily write the code for Case 4. Here’s the idea:

• GetPrevNode () getPrevNode() getPrevNode() getPrevNode
• Add a new node after the pre.

The following is the specific operation process of Case 1 to 4:

MyLinkedList.prototype.addAtIndex = function(index, val) {
  if (index > this.length) {
    // Case 1. If index is greater than the length of the linked list, the node will not be inserted.
    return;
  } else if (index == this.length) {
    // Case 2. If index is equal to the length of the list, this node is appended to the end of the list.
    this.addAtTail(val);
  } else if (index <= 0) {
    // Case 3. Insert a node in the header if index is less than 0.
    this.addAtHead(val);
  } else {
    // Case 4.
    // Get the node pre before index
    const pre = this.getPreNode(index);
    // Add a new node after the pre
    const p = new listNode(val);
    p.next = pre.next;
    pre.next = p;
    // List length +1
    this.length++; }};Copy the code

(6) Delete a node

The node deletion operation is given the index to be deleted (the index starts from 0). There are two types of deletion:

• If index is not valid, then do nothing;
• If index is valid, then we delete this node.

Of the two cases above, Case 1 is easier to handle, and Case 2 is more difficult. If you want to delete an index node, you want to find the node in front of it. Once you have the front nodes, it’s much easier to delete the next nodes. But you already have the getPrevNode function, so it’s pretty easy to do.

The following is the specific operation process

MyLinkedList.prototype.deleteAtIndex = function(index) {
  // Case 1. If index is invalid, then do nothing.
  if (index < 0 || index >= this.length) {
    return;
  }
  // Case 2. Delete index node
  // Step 1. Find the node before index
  const pre = this.getPreNode(index);
  // Step 2. If you want to delete the last node, change the tail pointer
  if (this.tail == pre.next) {
    this.tail = pre;
  }
  // step. 3 Perform the deletion. And modify the length of the list.
  pre.next = pre.next.next;
  this.length--;
};
Copy the code

(7) Summary

The total code for implementing the linked list using dummy nodes is as follows:

        /**
* Initialize your data structure here.
*/
var listNode = function(val) {
    this.val = val
    this.next = null
};

var MyLinkedList = function() {
    this.dummy = new listNode()
    this.tail = this.dummy
    this.length = 0
};


/**
* Get the value of the index-th node in the linked list. If the index is invalid, return -1. 
* @param {number} index
* @return {number}* /
MyLinkedList.prototype.getPreNode = function(index) {
    if (index < 0 || index >= this.length) {
      return -1;
    }
    // Initialize front and back, respectively
    let front = this.dummy.next
    let back = this.dummy
    // When searching, front and back always walk together
    for (let i = 0; i < index && front ! =null; i++) {
      back = front;
      front = front.next;
    }
    // Set back as prev and return
    return back
};

MyLinkedList.prototype.get = function(index) {
    if (index < 0 || index >= this.length) {
      return -1;
    }
    
    return this.getPreNode(index).next.val
};

/**
* Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. 
* @param {number} val
* @return {void}* /
MyLinkedList.prototype.addAtHead = function(val) {
    // Generate a node with the value val
    const p = new listNode(val)
    // Point p.next to the first node
    p.next = this.dummy.next;
    Dummy. Next refers to the new node, making it the first node
    this.dummy.next = p;
    // Modify the tail pointer when adding nodes.
    if (this.tail == this.dummy) {
      this.tail = p;
    }
    // List length +1
    this.length ++
};

/**
* Append a node of value val to the last element of the linked list. 
* @param {number} val
* @return {void}* /
MyLinkedList.prototype.addAtTail = function(val) {
    // Add a new node to the end
    this.tail.next = new listNode(val)
    // Move the tail pointer
    this.tail = this.tail.next;
    // List length +1
    this.length ++
};

/** * Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list,  the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. *@param {number} index 
* @param {number} val
* @return {void}* /
MyLinkedList.prototype.addAtIndex = function(index, val) {
  if (index > this.length) {
    // Case 1. If index is greater than the length of the linked list, the node will not be inserted.
    return;
  } else if (index == this.length) {
    // Case 2. If index is equal to the length of the list, this node is appended to the end of the list.
    this.addAtTail(val);
  } else if (index <= 0) {
    // Case 3. Insert a node in the header if index is less than 0.
    this.addAtHead(val);
  } else {
    // Case 4.
    // Get the node pre before index
    const pre = this.getPreNode(index);
    // Add a new node after the pre
    const p = new listNode(val);
    p.next = pre.next;
    pre.next = p;
    // List length +1
    this.length++; }};/**
* Delete the index-th node in the linked list, if the index is valid. 
* @param {number} index
* @return {void}* /
  
  
MyLinkedList.prototype.deleteAtIndex = function(index) {
  // Case 1. If index is invalid, then do nothing.
  if (index < 0 || index >= this.length) {
    return;
  }
  // Case 2. Delete index node
  // Step 1. Find the node before index
  const pre = this.getPreNode(index);
  // Step 2. If you want to delete the last node, change the tail pointer
  if (this.tail == pre.next) {
    this.tail = pre;
  }
  // step. 3 Perform the deletion. And modify the length of the list.
  pre.next = pre.next.next;
  this.length--;
};

/** * Your MyLinkedList object will be instantiated and called as such: * var obj = new MyLinkedList() * var param_1 = obj.get(index) * obj.addAtHead(val) * obj.addAtTail(val) * obj.addAtIndex(index,val) * obj.deleteAtIndex(index) */
Copy the code

To initialize the head without using dummy nodes, the code looks like this:

/** * Initialize your data structure here. */
var MyLinkedList = function() {
  this.head=null
  this.rear=null
  this.len=0
};
function ListNode(val) {
  this.val = val;
  this.next = null;
}
/**
 * Get the value of the index-th node in the linked list. If the index is invalid, return -1. 
 * @param {number} index
 * @return {number}* /
MyLinkedList.prototype.get = function(index) {
  if(index<0||index>this.len-1)
    return -1
  var node=this.head
  while(index-->0) {if(node.next==null)
      return -1
    node=node.next
  }
  return node.val
};

/**
 * Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. 
 * @param {number} val
 * @return {void}* /
MyLinkedList.prototype.addAtHead = function(val) {
  var node=new ListNode(val)
  if(this.head==null)
    this.rear=node
  else
    node.next=this.head
  this.head=node
  this.len++
};

/**
 * Append a node of value val to the last element of the linked list. 
 * @param {number} val
 * @return {void}* /
MyLinkedList.prototype.addAtTail = function(val) {
  var node=new ListNode(val)
  if(this.head==null)
    this.head=node
  else
    this.rear.next=node
  this.rear=node
  this.len++
};

/** * Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list,  the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. *@param {number} index 
 * @param {number} val
 * @return {void}* /
MyLinkedList.prototype.addAtIndex = function(index, val) {
  if(index<=0)
    return this.addAtHead(val)
  if(this.len<index)
    return
  if(index==this.len)
    return this.addAtTail(val)
  var node=this.head
  while(index-->1){
    node=node.next
  }
    
  var newnode=new ListNode(val)
  newnode.next=node.next
  node.next=newnode
  this.len++
};

/**
 * Delete the index-th node in the linked list, if the index is valid. 
 * @param {number} index
 * @return {void}* /
MyLinkedList.prototype.deleteAtIndex = function(index) {
  if(index<0||index>this.len-1||this.len==0)
    return
  if(index==0) {this.head=this.head.next
    this.len--
    return
  }

  var node=this.head
  var myindex=index
  while(index-->1){
    node=node.next
  }
  if(myindex==(this.len-1)) {this.rear=node
  }
  node.next=node.next.next
  this.len--
};

/** * Your MyLinkedList object will be instantiated and called as such: * var obj = new MyLinkedList() * var param_1 = obj.get(index) * obj.addAtHead(val) * obj.addAtTail(val) * obj.addAtIndex(index,val) * obj.deleteAtIndex(index) */
Copy the code

When you compare these two pieces of code, you can see that using dummy nodes is much simpler.

3. The properties of linked lists

(1) Circular linked list

Given a linked list, determine whether there are rings in the list.

To represent the loop in a given list, we use the integer POS to represent where the end of the list is joined into the list (the index starts at 0). If pos is -1, there are no rings in the list.

Example 1:

Type: head = [3.2.0, -4], pos = 1Output:true
Copy the code

Explanation: There is a loop in a linked list with a second node at the end.

Example 2:

Type: head = [1.2], pos = 0Output:true
Copy the code

Explanation: There is a loop in a linked list, and the end of the loop is connected to the first node.

Example 3:

Type: head = [1], pos = -1Output:false
Copy the code

Explanation: There are no rings in a linked list.

Advanced: Can you solve this problem with O(1) (i.e., constant) memory?

We only need to mark each traverse the nodes (because each node is an object here, so is equivalent to traverse the nodes, set a flag properties for him, if this attribute is exist in the traverse the nodes that form the loop), the back if I encounter it again, that has a ring, simply return true:

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} head
 * @return {boolean}* /
var hasCycle = function(head) {
    while(head){
        if(head.flag){
            return true
        }else{
            head.flag = true
            head = head.next
        }
    }
    return false
};
Copy the code

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the list, in the worst case we have to traverse the entire list;
• Space complexity: O(n), where n is the number of nodes in the list, mainly the hash table overhead, in the worst case, each node needs to be inserted into the hash table once.

(2) Ring linked list II

Given a linked list, return the first node where the list started to enter the loop. Null is returned if the list is loopless.

To represent the loop in a given list, we use the integer POS to represent where the end of the list is joined into the list (the index starts at 0). If pos is -1, there are no rings in the list.

Note: Modifications to the given list are not allowed.

Example 1:

Type: head = [3.2.0, -4], pos = 1Output: tail connects to node index1Explanation: There is a loop in a linked list with a second node at the end.Copy the code

Example 2:

Type: head = [1.2], pos = 0Output: tail connects to node index0Explanation: There is a loop in a linked list, and the end of the loop is connected to the first node.Copy the code

Example 3:

Type: head = [1], pos = -1Output: no cycle Description: There is no loop in the list.Copy the code

Advanced: Can you solve this problem without extra space?

Set a flag, but return a different value. The last point is the node with flag, so return head directly.

The above method needs to open up O(n) storage space to store the marker information, so we try to use the fast and slow Pointers to solve this problem: set two Pointers, the fast pointer travels two nodes each time, and the slow pointer travels one node each time. If there is a loop, then the two Pointers must meet. After the fast and slow Pointers meet, we use another pointer to find the location where they meet.

Setting identification method:

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} head
 * @return {ListNode}* /
var detectCycle = function(head) {
    while(head){
        if(head.flag){
            return head
        }else{
            head.flag = true
            head = head.next
        }
    }
    return null
};
Copy the code

Fast and slow pointer method:

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} head
 * @return {ListNode}* /
var detectCycle = function(head) {
    let fast = head
    let slow = head
    let cur = head

    while(fast && fast.next && fast.next.next){
        slow = slow.next
        fast = fast.next.next
        if(fast == slow){
            while(cur! =slow){ cur = cur.next slow = slow.next }return slow
        }
    }
    return null
};
Copy the code

Complexity analysis of setting identification method:

• Time complexity: O(n), where n is the number of nodes in the list, in the worst case we have to traverse the entire list;
• Space complexity: O(n), where n is the number of nodes in the list, mainly the hash table overhead, in the worst case, each node needs to be inserted into the hash table once.

Complexity analysis of fast-slow pointer method:

• Time complexity: O(n), where n is the number of nodes in the list. In the initial judgment of whether the fast and slow Pointers meet, the distance traveled by the slow pointer does not exceed the total length of the list; Later, when looking for the entry point, the distance traveled will not exceed the total length of the list. Therefore, the total execution time is O(N)+O(N)=O(N).
• Space complexity: O(1). We only used slow, fast, and cur.

(3) Intersecting linked list

Write a program to find the starting node where two singly linked lists intersect.

Here are two linked lists:

It intersects at node C1.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA= 2, skipB = 3 Reference of the node with value = 8 Input description: The value of the intersecting node is 8. Starting from their respective table heads, list A is [4,1,8,4,5] and list B is [5,0,1,8,4,5]. In A, there are two nodes before the intersection node; In B, there are three nodes before the intersection node.

Example 2:

IntersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 Reference of the node with value = 2 Input description: The value of the intersecting node is 2. Counting from the respective table headers, list A is [0,9,1,2,4] and list B is [3,2,4]. In A, there are three nodes before the intersection node; In B, there is 1 node before the intersection node.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB= 2 Starting from their respective table headers, list A is [2,6,4] and list B is [1,5]. Since these two linked lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values. Explanation: The two lists do not intersect, so null is returned.

Note:

• If two lists do not intersect, null is returned.
• After the results are returned, the two lists must retain their original structure.
• It can be assumed that there are no loops in the entire list structure.
• The program tries to meet the O(n) time complexity and only uses O(1) memory.

A more straightforward way to do this is to use double Pointers, and the idea is to make the list ab and BA so that the height difference between the two is eliminated, and if a and B intersect, then ab and BA must intersect. The specific implementation steps are as follows:

• Define two Pointers pA and pB;
• PA starts from the head of the list A, and then starts from the head of the list B;
• PB starts from the head of the list B, and then starts from the head of the list A;
• If there is a point of intersection you just return pA or pB

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}* /
var getIntersectionNode = function(headA, headB) {
    let pA = headA
    let pB = headB
    while(pA ! == pB){ pA = pA ===null ? headB : pA.next
        pB = pB === null ? headA : pB.next
    }
    return pA
};
Copy the code

Complexity analysis:

• Time complexity: O(m + n), where m and n are the number of nodes of two linked lists, and in the worst case, two lists need to be traversed.
• Space complexity: O(1), node Pointers A, B use constant size of extra space.

(4) The middle node of the linked list

Given a non-null single linked list with head, return the middle node of the list. If there are two intermediate nodes, the second intermediate node is returned.

Example 1:

Input:1.2.3.4.5] Output: the nodes in this list3(Serialized form: [3.4.5]) returns the value of3. (The evaluation system describes the node serialization as [3.4.5]). Note that we return an object of type ListNode, ans, as follows: ans.val =3, ans.next.val = 4, ans.next.next.val = 5, and ans.next. Next = NULL.Copy the code

Example 2:

Input:1.2.3.4.5.6] Output: the nodes in this list4(Serialized form: [4.5.6]) since the list has two intermediate nodes, the value is3 和 4We return the second node.Copy the code

Tip: The number of nodes in a given list is between 1 and 100.

For this kind of problem, we can use the fast pointer to achieve, initialize the slow and fast Pointers, both of which start at the head node. And then the slow pointer goes one step at a time, and the fast pointer goes two steps at a time, so that by the time the fast pointer goes through the list, the slow pointer is right in the middle of the list.

During the walk, if the last node of the fast pointer is empty, the walk ends and the value of the slow pointer is returned.

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var middleNode = function(head) {
    let fast = head, slow = head

    while(fast && fast.next){
        slow = slow.next
        fast = fast.next.next
    }
    return slow
};
Copy the code

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in a given list.
• Space complexity: O(1), only constant space is needed to store itslow 和 fastTwo Pointers.

(5) Palindrome linked list

Please determine whether a linked list is a palindrome list.

Example 1:

Input:1->2Output:false
Copy the code

Example 2:

Input:1->2->2->1Output:true
Copy the code

Advanced: Can you solve this problem with O(n) time complexity and O(1) space complexity?

1) String concatenation: For this problem, the most direct idea is to traverse the list, at the same time forward and reverse concatenation of the list nodes, and finally compare the two concatenated strings are the same. 台湾国

2) Recursive traversal:

• First, define a global pointer with head as its initial value to be used for ordering traversal
• The recursive function is then called to iterate the list in reverse order, stopping when the header node is NULL
• Return true if the values of the nodes traversed in the positive order and the values of the nodes traversed in the reverse order are equal, and false otherwise

1) String concatenation:

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {boolean}* /
var isPalindrome = function(head) {
    let a = ""
    let b = ""
    while(head){
        const nodeVal = head.val
        a = a + nodeVal
        b = nodeVal + b
        head = head.next
    }
    return a === b
};
Copy the code

Recursive traversal:

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {boolean}* /


let pointer
function fn(head) {
    if(! head)return true
    const res = fn(head.next) && (pointer.val === head.val)

    pointer = pointer.next
    return res
} 

var isPalindrome = function(head) {
    pointer = head
    return fn(head)
};
Copy the code

String concatenation complexity analysis:

• Time complexity: O(n), where n refers to the number of elements in the list, we need to traverse the entire list.
• Space complexity: O(1), where only constant space is needed to hold two concatenated strings.

Recursive traversal complexity analysis:

• Time complexity: O(n), where n refers to the size of the list.
• Space complexity: O(n), where n refers to the size of the list, and the depth of the recursive stack is n in the worst case.

(6) Linked list components

Given a linked list node head, each node on the list has a unique integer value. Also given is a list G, which is a subset of the integral values in the list above. Returns the number of components in list G, where components are defined as the set of the values of the longest continuous node in the list (which must be in list G).

Example 1:

Input: the head:0->1->2->3
G = [0.1.3] output:2Explanation: In the linked list,0 和 1Is connected, and G does not contain2So [0.1Is a component of G, similarly [3] is also a component, so return2.Copy the code

Example 2:

Input: the head:0->1->2->3->4
G = [0.3.1.4] output:2Explanation: In the linked list,0 和 1Is connected,3 和 4Are connected, so [0.1] and [3.4] is two components, so return2.Copy the code

Tip:

• ifNIs a given linked listheadThe length of the1 <= N <= 10000.
• The value range of each node in the linked list is[0, N - 1].
• 1 <= G.length <= 10000
• GIs a subset of the values of all nodes in the list.

For this problem. There are two key points:

• Components must be sequential nodes in a linked list
• G contains each value of successive nodes, and if discontinuities occur, the result is +1

Based on these two points, we can define a representation, let’s call it isComponent for the moment. If G has this value, and isComponent is false, then this is a new component and the result is added by one. If G does not have this value, set isComponent to false. Move the pointer back one bit to continue the traversal. As long as the current pointer exists, the list is traversed until the entire list is traversed.

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @param {number[]} G
 * @return {number}* /
var numComponents = function(head, G) {
    let cur = head
    let isComponent = false
    let res = 0

    while(cur){
        if(G.indexOf(cur.val) > -1) {if(! isComponent){ isComponent =true
                res++
            }
        }else{
            isComponent = false
        }
        cur = cur.next
    }
    return res
};
Copy the code

Complexity analysis:

• Time complexity: O(m+n), here need to traverse the entire list and array, so the time complexity is O(m+n), where m is the number of elements in the list, n is the number of elements in G;
• Space complexity: O(1). Additional constant size auxiliary space is required.

(7) The KTH reciprocal node in the linked list

Input a linked list, output the KTH node in the list. In order to conform to the habits of most people, this question starts with 1, that is, the last node of the list is the penultimate node.

For example, a linked list has six nodes, starting from the starting node, and their values are 1, 2, 3, 4, 5, 6. The second-to-last node in the list is the node with the value 4.

Example:

Given a linked list:1->2->3->4->5, and k =2.Returns the list4->5.
Copy the code

To solve this problem, we can use the fast and slow Pointers, initializing the slow and fast Pointers, both of which start at the head of the list.

First, let the fast pointer go first, k nodes backwards, so that the difference between the fast pointer and the slow pointer is K nodes. After that, both Pointers move back at the same time until the fast pointer moves to the last node. At this time, since there are k nodes between the fast and slow Pointers, the node pointed to by the slow pointer is the KTH reciprocal node.

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @param {number} k
 * @return {ListNode}* /
var getKthFromEnd = function(head, k) {
    let slow = head, fast = head;
    let cur = 0;
    while(cur < k){
        fast = fast.next
        cur++
    }

    while(fast){
        fast = fast.next
        slow = slow.next
    }
    return slow

};
Copy the code

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the list, we need to traverse the whole list;
• Space complexity: O(n), where n is the number of nodes in the list, we need to store the list with two Pointers;

4. Classic topic: The operation of linked lists

(1) Add two numbers

Two non-empty lists are given to represent two non-negative integers. Where their respective bits are stored in reverse order, and each node can store only one digit.

If we add these two numbers, we will return a new linked list representing their sum. You can assume that neither of these numbers starts with 0, except for the number 0.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) output:7 -> 0 -> 8The reason:342 + 465 = 807
Copy the code

This is a linked list operation, where we can go through two lists, adding each node in turn. When you get the result of the addition, you take the units digit as the result of the current digit, and if you have the tens digit, you carry the tens digit to the next addition, and you get the final result.

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}* /
var addTwoNumbers = function(l1, l2) {
    const l3 = new ListNode(0)  // The linked list to hold the results
    let p1 = l1 // Define two Pointers to traverse the list
    let p2 = l2
    let p3 = l3 // Define two Pointers to the list of results
    let carry = 0  // Record the carry value after each addition
    while(p1 || p2){
        const v1 = p1 ? p1.val : 0
        const v2 = p2 ? p2.val : 0 
        const val = v1 + v2 + carry // 
        carry = Math.floor(val/10)  // Calculate the carry value
        p3.next = new ListNode(val % 10) // Take the value of the ones bit as the result of the current bit
        if(p1) p1 = p1.next   // Point the pointer to the next node
        if(p2) p2 = p2.next
        p3 = p3.next
    }
    // If there is a carry value at the end, put it directly in the result list
    if(carry){
        p3.next = new ListNode(carry)
    }
    return l3.next
};
Copy the code

Complexity analysis:

• Time complexity: O(Max (m, n)), where m and n are lengths of two linked lists, and we need to traverse each list.
• Space complexity: O(1). Additional constant size auxiliary space is required.

(2) Add the two numbers

I give you two non-empty lists to represent two non-negative integers. The highest digit is at the beginning of the list. They store only one digit per node. Adding these two numbers returns a new linked list. You can assume that neither of these numbers starts with zero except the number zero.

Advanced: What if the input list cannot be modified? In other words, you can’t flip the nodes in the list.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) output:7 -> 8 -> 0 -> 7
Copy the code

For this problem, we can use two stacks to store the elements push of the two linked lists respectively, and then add the corresponding elements of the two arrays starting from the ones bit. The detailed steps are as follows:

• Stack1 and Stack2 stacks are initialized, and the two lists are traversed to store the list elements.
• Initialize an empty node, dummyHead, to store the value of the new list;
• The two stacks are traversed, and the elements are taken from the end of the stack and added. The parts over 10 are carried, and the parts less than 10 are placed in the result list dummyHead as the sum of the current points
• The traversal ends when both stacks are empty
• And finally, if there’s a carry value after the last addition, add it to the list

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}* /
var addTwoNumbers = function(l1, l2) {
    let stack1 = [], stack2 = [];

    while(l1){
        stack1.push(l1)
        l1 = l1.next
    }
    while(l2){
        stack2.push(l2)
        l2 = l2.next
    }

    let dummyHead = {next: null}
    let carry = 0

    while(stack1.length || stack2.length){
        let p1 = stack1.pop()
        let p2 = stack2.pop()

        let x = p1 ? p1.val : 0
        let y = p2 ? p2.val : 0

        let sum = x + y + carry
        let m = sum % 10   / / bits
        let n = Math.floor(sum / 10)
        dummyHead.next = { val: m, next: dummyHead.next}
        carry = n
    }

    if(carry){
        dummyHead.next =  { val: carry , next: dummyHead.next };
    }
    return dummyHead.next
};
Copy the code

Complexity analysis:

• Time complexity: O(Max (m, n)), where m and n are lengths of two linked lists, and we need to traverse each list.
• Space complexity: O(m + n), where m and n are the lengths of the two lists, and this is the space used to put the list contents into the stack.

(3) Reverse the linked list

Inverts a single linked list. Example:

Input:1->2->3->4->5- > NULL output:5->4->3->2->1->NULL
Copy the code

Advanced: You can iterate or recursively reverse a linked list. Can you solve this problem in two ways?

When we operate on a list, we are actually operating on a pointer to the list. Therefore, for this problem, the most direct method is to point the pointer of each node to the precursor node of that node, so the whole list is reversed, and three Pointers need to be set: respectively pointing to the precursor node, the current node, and the rear node.

Try again using recursion to implement this topic:

In this case, the most important operation is the inversion operation: the current node is head, and the next node is head.next. We only need to point head.next to head to achieve inversion. Finally, simply disconnect the pointer between head and head.next, and the pointer inversion between the two nodes is achieved. Finally, perform the above steps recursively.

Set the precursor node:

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function(head) {
    // Set the pointer to the precursor node and the current node
    let pre = null
    let cur = head
    // Iterate through the list until the list node is empty
    while(cur! =null) {// Record the current node for later traversal
        let next = cur.next
        // Turn the pointer to the list
        cur.next = pre
        // Move the pointer backwards
        pre = cur
        cur = next
    }
    return pre
};
Copy the code

Recursive traversal:

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function(head) {
    // The list is empty or has only one node
    if(! head || ! head.next){return head
    }
    // Store the next node for later recursion
    let next = head.next
    / / recursion
    let result = reverseList(next)
    // Disconnect the current node from its rear-drive node
    head.next = null 
    // Make the next node the current node
    next.next = head
    return result
};
Copy the code

Set the precursor node complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the list, we need to traverse the whole list;
• Space complexity: O(1), where we only need constant space to store Pointers.

Recursive traversal complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the list;
• Space complexity: O(n), where n is the number of nodes in the list, and the depth of the recursion stack is n in the worst case.

(4) Reverse linked list II

Inverts the list from position m to n. Use one scan to complete the reversal. Note: 1 ≤ M ≤ N ≤ Length of the list.

Example:

Input:1->2->3->4->5->NULL, m = 2, n = 4Output:1->4->3->2->5->NULL
Copy the code

The main thing in this problem is to reverse the nodes from m to n, and then the m-1 node points to n, and the n+1 node points to m, so as to achieve the local inversion of the list.

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}* /
var reverseBetween = function(head, m, n) {
   // Define the virtual header node
   let dummy = new ListNode()
   dummy.next = head
   // Look for the m-1 node
   let p = dummy
   for(let i =0; i<m-1; i++){
       p= p.next
   }
   // Define the current node and the precursor node. The current node points to the m node
   let pre = null 
   let cur = p.next
   // Invert the m to N nodes
   for(let i = 0; i<= n-m; i++){
       let next = cur.next
       cur.next = pre
       pre = cur
       cur = next
   }
   // Concatenate the inverted local list with the original list
   p.next.next = cur
   p.next = pre
   
   return dummy.next
};
Copy the code

Complexity analysis

• Time complexity: O(n), where n is the number of nodes in the list. In the worst case, you need to traverse the entire list.

• Space complexity: O(1). Additional constant size auxiliary space is required.

(5) Rotating linked list

Given a linked list, rotate the list, moving each node of the list k positions to the right, where K is non-negative.

Example 1:

Input:1->2->3->4->5->NULL, k = 2Output:4->5->1->2->3->NULL1Step:5->1->2->3->4->NULL rotates to the right2Step:4->5->1->2->3->NULL
Copy the code

Example 2:

Input:0->1->2->NULL, k = 4Output:2->0->1->NULL1Step:2->0->1->NULL rotates to the right2Step:1->2->0->NULL rotates to the right3Step:0->1->2->NULL rotates to the right4Step:2->0->1->NULL
Copy the code

For this problem, a very direct idea is to convert the single linked list into a circular linked list, and then move the list to break the single linked list after the completion of the realization of the steps are mainly three steps:

• First, traverse the list, find the tail node of the list, and connect the tail node and head node, so as to form a circular linked list;
• They say that moving k steps to the right, in this case we’re moving the tail node to the left, is equivalent to moving length minus k steps to the left;
• Finally, after the movement is complete, the end node of the list is found and the circular list is broken into a unidirectional list.

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @param {number} k
 * @return {ListNode}* /
var rotateRight = function(head, k) {
    if(! head || ! head.next){return head
    }
    // Find the tail node and form the single linked list into a circular list
    let tail = head
    let length = 1
    while(tail.next){
        length++
        tail = tail.next
    }
    tail.next = head
    // Move the tail node
    k = k % length
    for(let i = 0; i < length - k; i++){
        tail = tail.next
    }
    // Find the head node and break the ring list
    head = tail.next
    tail.next = null
    return head
};
Copy the code

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the list;
• Space complexity: O(1). Additional constant size auxiliary space is required.

(6) A group of K to flip the linked list

I give you a list, and I flip it every k nodes, and I ask you to return the list. K is a positive integer whose value is less than or equal to the length of the list. If the total number of nodes is not an integer multiple of K, leave the last remaining nodes in their original order.

Example:

Here's the list:1->2->3->4->5When k =2Should return:2->1->4->3->5When k =3Should return:3->2->1->4->5
Copy the code

Description:

• Your algorithm can only use constant extra space.
• You can’t just change the values inside a node, but actually switch nodes.

One idea is to use a recursive solution:

• Enable a counter to intercept the first K nodes of the list
• Reverse the list
• Recursively, the last node in the last pass is used as the current start node

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @param {number} k
 * @return {ListNode}* /
var reverseKGroup = function(head, k) {
    let cur = head
    let count = 0

    while(cur ! = =null&& count ! == k){ cur = cur.next count++ }if(count == k){
        cur = reverseKGroup(cur, k)
        // Flip the list
        while(count ! = =0){
            count-- 
            let tmp = head.next
            head.next = cur
            cur = head
            head = tmp
        }
        head = cur
    }
    return head
};
Copy the code

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the list;
• Space complexity: O(1). Additional constant size auxiliary space is required.

(7) Switch nodes in the linked list in pairs

Given a linked list, swap the adjacent nodes in pairs and return the swapped list. You can’t just change the values inside a node, but actually switch nodes.

Example 1:

Type: head = [1.2.3.4] Output: [2.1.4.3]
Copy the code

Example 2:

Input: head = []Copy the code

Example 3:

Type: head = [1] Output: [1]
Copy the code

Tip:

• The number of nodes in the list is in the range [0, 100]
• 0 <= Node.val <= 100

Advanced: Can you solve this problem without changing the list node values? (That is, only the node itself is modified.)

For this problem, we can use both iterative and recursive methods:

(1) recursive implementation in the process of recursion, its termination condition is that there is no node in the list, or only one node in the list, can not be exchanged.

For the two nodes in the list, the original head node becomes the second node after the two nodes are switched, and the original second node becomes the new head node, and the exchange of the remaining nodes can be realized through recursion.

(2) Implementation of iteration For iteration, we can create a list of dummy nodes and point this node to the head node of the node given in the problem. Initialize a temp to hold the dummy node with an initial value of list, swapping the two nodes following temp each time. The switching can be performed only when there are at least two nodes behind the Temp node. Otherwise, the switching is terminated. During the exchange, obtain the two nodes behind temp and update the pointer relationship of the nodes to realize the exchange of the two nodes. After the two nodes are switched, update the temp node to the second node, namely Node1.

Recursive implementation:

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var swapPairs = function(head) {
    if(! head || ! head.next){return head
    }
    const newHead = head.next  // Get the second node
    head.next = swapPairs(newHead.next) // Recursively swap the remaining nodes
    newHead.next = head  // The node is switched
    return newHead
};
Copy the code

Iterative implementation:

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var swapPairs = function(head) {
    if(! head || ! head.next){return head
    }
    const list = new ListNode(0)
    list.next = head

    let temp = list

    while(temp.next && temp.next.next){
        const node1 = temp.next
        const node2 = temp.next.next
        // Node1 and Node2 are switched
        temp.next = node2
        node1.next = node2.next
        node2.next = node1
        // Update the temp node
        temp = node1
    }
    return list.next
};
Copy the code

Complexity analysis of recursion:

• Time complexity: O(n), where n is the number of nodes in the list. You need to update the pointer on each node.
• Space complexity: O(n), where n is the number of nodes in a linked list. The spatial complexity depends primarily on the stack space of the recursive call.

Complexity analysis of iteration:

• Time complexity: O(n), where n is the number of nodes in the list. You need to update the pointer on each node.
• Space complexity: O(1). Additional constant size auxiliary space is required.

(8) Switch nodes in the linked list

I give you the head node of the list, head, and an integer k.

After swapping the values of the positive KTH and reciprocal KTH nodes of the list, the head node of the list is returned (the list is indexed from 1).

Example 1:

Type: head = [1.2.3.4.5], k = 2Output:1.4.3.2.5]
Copy the code

Example 2:

Type: head = [7.9.6.6.7.8.3.0.9.5], k = 5Output:7.9.6.6.8.7.3.0.9.5]
Copy the code

Example 3:

Type: head = [1], k = 1Output:1]
Copy the code

Example 4:

Type: head = [1.2], k = 1Output:2.1]
Copy the code

Example 5:

Type: head = [1.2.3], k = 2Output:1.2.3]
Copy the code

Tip:

• The number of nodes in the list isn
• 1 <= k <= n <= 10
• 0 <= Node.val <= 100

For this problem, we can use the fast pointer to solve, the specific implementation idea is as follows:

• Dummy = dummy; dummy = dummy; dummy = dummy; dummy = dummy; dummy = dummy;
• To initialize slow and fast, both point to dummy, and initialize a pointer to save the KTH value;
• First, let the fast pointer and cur move K steps, while the slow pointer remains unchanged. In this case, cur points to the KTH value, and there are K steps between the fast and slow Pointers.
• Let the fast and slow Pointers walk together until the end of the fast pointer. Since there are k steps between the two, the slow pointer points to the KTH node
• Swap the element pointed to by the slow pointer, which is the KTH element, with cur, which is the KTH element;
• Finally, return the linked list head node head.

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @param {number} k
 * @return {ListNode}* /
var swapNodes = function(head, k) {
    let dummy = new ListNode(0)
    dummy.next = head

    let i = 0, cur = dummy
    let slow = dummy, fast =dummy

    while(i++ < k){
        fast = fast.next
        cur = cur.next
    }

    while(fast){
        fast = fast.next
        slow = slow.next
    }

    let temp = cur.val
    cur.val = slow.val
    slow.val = temp

    return head
};
Copy the code

Complexity analysis:

• Time complexity: O(n). Among themnIs the length of the list. In the worst case, we need to traverse the whole list.
• Space complexity: O(1). Additional constant size auxiliary space is required.

(9) Separate the linked list

Given a linked list and a specific value x, you separate the list so that all nodes less than x appear before nodes greater than or equal to x. You should preserve the initial relative position of each node in the two partitions.

Example:

Enter: head =1->4->3->2->5->2, x = 3Output:1->2->2->4->3->5
Copy the code

A straightforward way to think about this problem is to initialize two lists, one for values less than x and one for values greater than x.

Two linked lists are initialized: mallHead and largeHead. These two are dummy nodes of the list, that is, their next pointer points to the head node of the list, in order to make it easier to handle boundary conditions where the head node is empty.

At the end of the walk, the next pointer of large is set to null. This is because the current node is reuse of the original list node, and its next pointer may point to a node less than x. We need to break this reference. At the same time, the next pointer of small points to the node pointed to by the next pointer of largeHead, that is, the head node of the large linked list in the real sense. Returning smallHead’s next pointer is the final answer.

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @param {number} x
 * @return {ListNode}* /
var partition = function(head, x) {
    let small = new ListNode(0)
    const smallHead = small
    let large = new ListNode(0)
    const largeHead = large

    while(head){
        if(head.val < x){
            small.next = head
            small = small.next
        }else{
            large.next = head
            large = large.next
        }
        head = head.next
    }

    large.next = null
    small.next = largeHead.next
    return smallHead.next
};
Copy the code

Complexity analysis:

• Time complexity: O(n), where n is the length of the original list because it is traversed once.
• Space complexity: O(1). Additional constant size auxiliary space is required.

(10) Separate the linked list

Given a linked list with the head node root, write a function to separate the list into K consecutive parts.

The lengths of each section should be as equal as possible: the length difference between any two sections should not be more than 1, which means that some sections may be null.

The K parts should be printed in the order they appear in the list, and the length of the first part should be greater than or equal to the length of the next part.

Returns a list of linked lists that comply with the above rules.

Example: 1 – > 2 – > 3 – > 4, k = 5 / / 5 results [[1], [2], [3], [4], null] * * example 1:

Enter: root = [1.2.3], k = 5Output: [[1], [2], [3],[],[]] Explanation: Input and output parts should be lists, not arrays. For example, the input node root val=1, root.next.val = 2, \root.next.next.val = 3And root), next, next, next =null. First output output[0] is the output [0].val = 1, output[0].next = null. The last element output[4] fornullWhich indicates that the last part of the list is empty.Copy the code

Example 2:

Enter: root = [1.2.3.4.5.6.7.8.9.10], k = 3Output: [[1.2.3.4], [5.6.7], [8.9.10[] Explanation: The input is divided into consecutive parts, each of which does not differ in length more than the other1.The length of the front part is greater than or equal to the length of the back part.Copy the code

Tip:

• rootLength range of:[0, 1000].
• Size range for each node input:[0, 999].
• kValue range of:50] [1,.

For this problem, we can first calculate the length of the list, and divide the list as evenly as possible. Then calculate the length of each child list: first calculate the average length of each child list is length/k, if not divisible, the remaining length% K elements, then the length of the first length% K child list plus one.

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} root
 * @param {number} k
 * @return {ListNode[]}* /
var splitListToParts = function(root, k) {
    let cur = root
    let length = 0
    while(cur){
        cur = cur.next
        length++
    }
    // The length of each term
    let width = Math.floor(length / k), curry = length % k
    let num, temp
    
    let res = new Array(k);
    for(let i = 0; i < k; i++) {
        // Calculate the length of the cut from the remaining list
        num = i < curry ? width + 1 : width
        // Cut num from the remaining list
        temp = cur = root;
        for(let j = 1; cur && j < num; j++) {
            cur = cur.next;
        }
        // Change the root point
        if(cur) {
            root = cur.next;
            cur.next = null;
        } else {
            root = null;
        }
        res[i] = temp;
    }
    return res
};
Copy the code

Complexity analysis:

• Time complexity: O(N + k), where N refers to the number of nodes in the list, and if k is large, many empty lists need to be added.
• Space complexity: O(Max (N, k)), the space required to store the answer.

(11) Rearrange the list

Given a single linked list L: L0→L1→… L0→Ln→L1→ L-1 →L2→ L-2 →…

You can’t just change the values inside a node, but actually switch nodes.

Example 1:

A given list1->2->3->4, rearranged as1->4->2->3.
Copy the code

Example 2:

A given list1->2->3->4->5, rearranged as1->5->2->4->3.
Copy the code

One way to think about this topic is:

• First, use the fast and slow Pointers to get the midpoint of the list
• Disconnect from the midpoint of the list, slow pointer to the first half of the list, fast pointer to the second half of the list
• Reverse the second half of the list, so that the fast pointer to the second half of the list after the reversal
• Add the nodes of the two lists together according to the rules specified in the question

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
    if(! head || ! head.next)return 
    let slow = head
    let fast = head
    
    // Get the intermediate nodes of the list
    while(fast && fast.next){
        slow = slow.next
        fast = fast.next.next ? fast.next.next : null
    }
    
    // Break the list from the middle point, fast points to the second half of the list, slow points to the first half of the list
    fast = slow.next
    slow.next = null
    slow = head
    
    // Reverse the second half of the list
    let pre = null
    let cur = fast
    while(cur){
        let temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp
    }

    // Point fast to the list after the latter part is reversed
    fast = pre

    // Merge the two lists as required
    while(fast){
        let slowNext = slow.next
        let fastNext = fast.next

        slow.next = fast
        fast.next = slowNext
        slow = slowNext
        fast = fastNext
    }
};
Copy the code

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the list, we need to traverse the whole list;
• Space complexity: O(1). Additional constant size auxiliary space is required.

(12) Sorted linked list

The list is sorted in order (n log n) time complexity and constant space complexity.

Example 1:

Input:4->2->1->3Output:1->2->3->4
Copy the code

Example 2:

Input: -1->5->3->4->0Output: -1->0->3->4->5
Copy the code

(1) Merge sort: The problem requires to sort the list in O(n log N) time complexity and constant level space complexity, just merge sort can meet the requirements.

The main ideas are as follows:

• Check whether the list has only one element, and return if it does
• Using the fast – slow pointer, find the middle node of the list
• Merge sort recursively for the first half and the second half of the list
• Finally, the two sublists are merged

(2) with the help of an array to achieve: we can use an array to achieve this problem, the list into an array, the array of the elements to sort. Once sorted, the array is converted back into a linked list.

Merge sort:

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var sortList = function(head) {
    // If the list is empty or has only one node, return it directly
    if(head === null || head.next === null) {return head
    }
    // Use the fast/slow pointer to get the middle value of the list
    let fast = head
    let slow = head
    while(slow.next && fast.next && fast.next.next){
        slow = slow.next
        fast = fast.next.next
    }
    // Split the list into two
    const middle = slow.next
    slow.next = null
    
    // Recursively merge the two lists
    const left = head
    const right = middle
    return merge(sortList(left), sortList(right))
};

function merge (left, right) {
    // Initialize an empty result node
    let res = new ListNode(null);
    // The current node
    let prev = res;   
    while (left && right) {
        // If the value on the left is less than the value on the right, the current node points to the left, and the left node points to the next node
        if (left.val < right.val) {
            [prev.next, left] = [left, left.next]
        }else {
        // If the value on the right is less than the value on the left, the current node points to the right node and the right node points to the next node
            [prev.next, right] = [right, right.next];
        }
        // The current node points to the next node
        prev = prev.next;
    }
    // If there are any remaining nodes, join them directly at the end of the resulting list
    prev.next = left ? left : right;
    return res.next;
}
Copy the code

With an array:

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var sortList = function(head) {
    if(head === null || head.next === null) {return head
    }
    let cur = head
    let index = 0
    const arr = []
    // Convert the list to an array
    while(cur){
        arr[index] = cur.val
        cur = cur.next
        index ++
    }
    // Sort the array
    arr.sort((a,b) = > a-b)
    // Convert the array to a linked list
    cur = head
    index = 0
    while(cur){
        cur.val = arr[index]
        index ++
        cur = cur.next
    }
    return head
};
Copy the code

Merge sort complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the list, we need to traverse the whole list;
• Space complexity: O(1). Additional constant size auxiliary space is required.

Using array complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the list, we need to traverse the whole list;
• Space complexity: O(n), where n is the length of the array.

(13) Remove list elements

Given a list with head and an integer val, remove all nodes in the list that satisfy node.val == val and return the new head Node.

Example 1:

Type: head = [1.2.6.3.4.5.6], val = 6Output:1.2.3.4.5]
Copy the code

Example 2:

Enter: head = [], val =1Output: []Copy the code

Example 3:

Type: head = [7.7.7.7], val = 7Output: []Copy the code

Tip:

• List of nodes in range[0, 10] 内
• 1 <= Node.val <= 50
• 0 <= k <= 50

For this topic, in itself, it is very simple, is to traverse the list, delete the specified value, but need to pay attention to, if it is need to delete the values in the list, delete directly, if you want to delete a node in the list of the head, this is the traversal, to avoid this situation, we can initialize a dumb nodes dummyHead, It’s an empty node, put it in front of the head node. So it’s not empty.

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @param {number} val
 * @return {ListNode}* /
var removeElements = function(head, val) {
    let dummyHead = new ListNode(0)
    dummyHead.next = head

    let pre = dummyHead, cur = head
    while(cur){
        cur.val == val ? pre.next = cur.next : pre = cur
        cur = cur.next
    }
    return dummyHead.next
};
Copy the code

Complexity analysis:

• Time complexity: O(n). Among themnIs the length of the list, and we need to traverse the entire list.
• Space complexity: O(1). Additional constant size auxiliary space is required.

(14) Remove duplicate elements from the sorted list

Given a collated list, remove all duplicate elements so that each element appears only once.

Example 1:

Input:1->1->2Output:1->2
Copy the code

Example 2:

Input:1->1->2->3->3Output:1->2->3
Copy the code

This is a simple question, CURD is the basic operation of the list, we just need to compare two adjacent nodes, if the values are equal, an element will be deleted, if not, directly backward move the pointer, repeat the above steps until the list through all the nodes.

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var deleteDuplicates = function(head) {
    let cur = head

    while(cur && cur.next){
        if(cur.val === cur.next.val){
            cur.next = cur.next.next
        }else{
            cur = cur.next
        }
    }
    return head
};
Copy the code

Complexity analysis:

• Time complexity: O(n). Among themnIs the length of the list, and we need to traverse the entire list.
• Space complexity: O(1). Additional constant size auxiliary space is required.

(15) Remove duplicate element II from the sorted list

Given a collated list, remove all nodes with duplicate numbers, leaving only the original list with non-recurring numbers.

Example 1:

Input:1->2->3->3->4->4->5Output:1->2->5
Copy the code

Example 2:

Input:1->1->1->2->3Output:2->3
Copy the code

Similar to the idea above, but there is more to consider here.

When we delete a node, we need to delete both the front-end and back-end nodes of the node. If we want to get the precursors of a node, we need to set up a virtual head node to do so. The virtual head node points to the real head node, so that every node has a precursors.

It is important to note that there may be more than two duplicate nodes, so we need to verify, iterate, and delete until there are no duplicate elements.

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var deleteDuplicates = function(head) {
    // Handle cases where the list has only 0 or 1 nodes
    if(! head||! head.next){return head
    }
    // Set the virtual header node
    let dummy = new ListNode()
    dummy.next = head
    // Set the current node
    let cur = dummy

    while (cur.next &&cur.next.next){
        if(cur.next.val === cur.next.next.val){
            // Save the value of the duplicate node
            let val =cur.next.val
            // Check whether there are other equal nodes
            while(cur.next &&cur.next.val === val)
            {
                cur.next = cur.next.next
            }
        }else{
            cur = cur.next
        }
    }
    // Return the final result, which is the starting node of the list
    return dummy.next
};
Copy the code

Complexity analysis:

• Time complexity: O(n). Among themnIs the length of the list, and we need to traverse the entire list.
• Space complexity: O(1). Additional constant size auxiliary space is required.

(16) Delete the NTH reciprocal node of the linked list

Given a linked list, remove the NTH reciprocal node of the list and return the head node of the list.

Example:

Given a linked list:1->2->3->4->5, and n =2.When the penultimate node is deleted, the list becomes1->2->3->5.
Copy the code

Note: The given n guarantee is valid. Advanced: Can you try using a scan implementation?

In this case, we can use the violent method of traversing the list twice, the first time to calculate the length of the list, the second time to delete the NTH element from the bottom, but this is bound to make the execution efficiency very low, we need to consider only traversing the list once.

If we are only going to iterate once, then we need to use double Pointers to solve this problem. Here we use the fast/slow pointer:

• Set the fast and slow Pointers, starting with the virtual head
• Let the fast pointer go first, to the NTH node
• Then the two Pointers walk together until the fast pointer guides the last node
• In this case, the node to which the slow pointer points is the NTH reciprocal node of the list
• Delete the corresponding node

Most importantly, the fast pointer and the slow pointer are always kept N nodes apart, which makes it easier to do later operations.

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @param {number} n
 * @return {ListNode}* /
var removeNthFromEnd = function(head, n) {
   // Set the virtual header node
   const dummy = new ListNode()
   dummy.next = head
   // Set the speed pointer
   let fast = dummy
   let slow = dummy
   // The fast pointer goes to the NTH node first
   while(n! = =0){
       fast = fast.next
       n--
   }
   // The fast and slow Pointers walk together until the fast pointer points to the last node
   while (fast.next){
       fast = fast.next
       slow = slow.next
   }
   // Delete the NTH node
   slow.next = slow.next.next
   return dummy.next
};
Copy the code

Complexity analysis:

• Time complexity: O(n). Among themnIs the length of the list, and we need to traverse the entire list.
• Space complexity: O(1). Additional constant size auxiliary space is required.

(17) Merge two ordered lists

Merge the two ascending lists into a new ascending list and return. The new list is formed by concatenating all the nodes of the given two lists.

Example:

Input:1->2->4.1->3->4Output:1->1->2->3->4->4
Copy the code

In fact, to deal with a list is to deal with the relationship between the lists of Pointers, these Pointers are like a line, all the data together to form a list.

We only need to compare the nodes of the two linked lists each time, and then let the current pointer point to a relatively small number, and then adjust the pointer to the number pointing to the back, so that the sequential comparison of the two nodes, we can achieve the sequential merger of the two linked lists.

Note that we need to consider the different lengths of the list. Since both lists are ordered, if one list is traversed and the other is not traversed, we can simply put the unfinished part at the end of the new list.

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}* /
var mergeTwoLists = function(l1, l2) {
    // Define the header node of the new list
    let head = new ListNode();
    // The current pointer points to the node
    let cur = head;

    while (l1&&l2){
        if(l1.val<=l2.val){
            // Point to the smaller node first
            cur.next = l1
            // Move the pointer
            l1 = l1.next
        }else{
            cur.next = l2
            l2 = l2.next
        }
        // When a node is connected, the pointer moves one bit
        cur = cur.next
    }
    // Handles the case where two lists have different lengthscur.next = l1! = =null ? l1 : l2
    // Return the final result. The location of the header pointer represents the newly generated list
    return head.next
};
Copy the code

Complexity analysis:

• Time complexity: O(n + m). Where m and n are the lengths of two linked lists, and we need to traverse the two lists.
• Space complexity: O(1). Additional constant size auxiliary space is required.

(18) Merge K ascending linked lists

You are given an array of linked lists, each of which has been sorted in ascending order.

Please merge all lists into an ascending list and return the merged list.

Example 1:

Input: lists = [[1.4.5], [1.3.4], [2.6[] Output: [1.1.2.3.4.4.5.6The list array is as follows:1->4->5.1->3->4.2->6] by combining them in an ordered linked list.1->1->2->3->4->4->5->6
Copy the code

Example 2:

Input: lists = [] Output: []Copy the code

Example 3:

Input: lists = [[]] Output: []Copy the code

Tip:

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 ascendingarrangement
• lists[i].lengthDoes not exceed10 ^ 4

For this problem, we can merge the lists two at a time, and when we’re done, update the array, and continue merging two at a time, using recursion.

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode[]} lists
 * @return {ListNode}* /
var mergeKLists = function(lists) {
    let len = lists.length
    if(! len){return null
    }
    if(len === 1) {return lists[0]}// Merge the first two items of the array first
    let res = mergeTwoKLists(lists[0], lists[1])
    // Update the array
    lists.splice(0.2, res)
    // Perform a recursive operation
    return mergeKLists(lists)
};

// Merge the two lists
function mergeTwoKLists(l1, l2){
    let head = new ListNode(), pre = head
    while (l1 && l2) {
        if (l1.val > l2.val) {
            pre.next = l2
            l2 = l2.next
        } else {
            pre.next = l1
            l1 = l1.next
        }
        pre = pre.next
    }
    pre.next = l1 ? l1 : l2
    return head.next
}
Copy the code

Complexity analysis:

• Time complexity: O(NlogK), the sum of K lists is N, and each list has N/K nodes on average, so the time complexity of merging two lists is O(N/K). Starting from K lists, two lists are merged into one list, so each list will be merged logK times, so K lists will be merged K * logK times, so the total time complexity is K * logK * N/K which is O(NlogK).
• Space complexity: O(1), no auxiliary space related to K and N scales is used, so the progressive space complexity is O(1).

(19) Copy a linked list with random Pointers

Given a list of length n, each node contains an additional pointer random, which can point to any node or null node in the list.

Construct a deep copy of the list. The deep copy should consist of exactly n new nodes, each of which has the same value as the original node. The next and random Pointers of the new node should also point to the new node in the replicated list, so that these Pointers in the original and replicated lists represent the same list state. No pointer in the copied list should point to a node in the original list.

For example, if the original list has two nodes X and Y, where x. randam –> Y. Then the corresponding two nodes x and y in the replicated list also have x. randam –> y. Returns the head node of the replicated list.

The linked list in the input/output is represented by a list of n nodes. Each node is represented by a [val, random_index] :

• val: a representationNode.valThe integer.
• random_index: Indicates the index of the node to which the random pointer points0 到 n-1); Or if it does not point to any nodenull 。

Your code only accepts the head node of the original list as an argument.

Example 1:

Type: head = [[7.null], [13.0], [11.4], [10.2], [1.0[] output: [[7.null], [13.0], [11.4], [10.2], [1.0]]
Copy the code

Example 2:

Type: head = [[1.1], [2.1[] output: [[1.1], [2.1]]
Copy the code

Example 3:

Type: head = [[3.null], [3.0], [3.null[] output: [[3.null], [3.0], [3.null]]
Copy the code

Example 4:

Input: head = [] Output: [] Explanation: The given list is null (null pointer), so returnnull.Copy the code

Tip:

• 0 <= n <= 1000
• -10000 <= Node.val <= 10000
• Node.randomIs null or points to a node in the list.

We can solve this problem in three steps:

1) The first step is to create the corresponding new node according to the traversed original node. Each newly created node is behind the original node. For example, the original node 1 in the figure below no longer points to the original node 2, but to the new node 1

2) The second step is the most critical and is used to set the random pointer to the new list

In the figure above, you can see a pattern

• The random pointer of the original node 1 points to the original node 3, and the random pointer of the new node 1 points to the next of the original node 3
• The random pointer of the original node 3 points to the original node 2, and the random pointer of the new node 3 points to the next of the original node 2

That is, a random pointer to the original node I, if any, points to the original node J. So the random pointer to the new node I is next to the original node J.

3) The third step is to separate the two lists and return the new list

/** * // Definition for a Node. * function Node(val, next, random) { * this.val = val; * this.next = next; * this.random = random; *}; * /

/ * * *@param {Node} head
 * @return {Node}* /
var copyRandomList = function(head) {
    if(! head){return null
    }

    let p = head
    // Create a new node after each of the original nodes
    while(p ! = =null) {let newNode = new Node(p.val)
        newNode.next = p.next
        p.next = newNode
        p = newNode.next
    }
    p = head
    // Set a random node for the new node
    while(p ! = =null) {if(p.random){
            p.next.random = p.random.next
        }
        p = p.next.next
    }
    let dummyHead = new Node(-1)
    p = head
    let cur = dummyHead
    // Separate the two lists
    while(p ! = =null){
        cur.next = p.next
        cur = cur.next
        p.next = cur.next
        p = p.next
    }
    return dummyHead.next
};
Copy the code

Complexity analysis:

• Time complexity: O(n), where n is the number of nodes in the list, we need to traverse the whole list.
• Space complexity: O(n), here we only need the space of constants.

(20) Insert sort for the linked list

Do insertion sort on a linked list.

An animation of insertion sort is shown above. Starting with the first element, the list can be considered partially sorted (shown in black). At each iteration, an element (represented in red) is removed from the input data and inserted in place into the sorted list.

Insertion sort algorithm:

1. Insertion sort is iterative, moving one element at a time until all elements can form an ordered output list.
2. On each iteration, insertion sort simply removes an element to be sorted from the input data, finds it at its appropriate place in the sequence, and inserts it.
3. Repeat until all input data has been inserted.

Example 1:

Input:4->2->1->3Output:1->2->3->4
Copy the code

Example 2:

Input: -1->5->3->4->0Output: -1->0->3->4->5
Copy the code

For a unidirectional linked list, there is only a pointer to the next node, so you need to start at the head node of the list and go through the nodes in the list to find the insertion position. The specific process of insertion sort for a linked list is as follows:

1. First, determine whether the given list is empty. If it is empty, it returns directly without sorting.
2. Create the dummy node dummyHead and set dummyHead.next = head. Dummy nodes are introduced to facilitate the insertion of nodes before the head node.
3. Maintain last as the last node in the sorted part of the list, initially with last = head.
4. Maintain cur as the element to be inserted, initially with cur = head.next.
5. Compare the node values of last and cur.

• If last. Val <= cur. Val, cur should be placed after last, and curr becomes the new last.
• Otherwise, starting at the head node of the list, you iterate through the nodes in the list to find where to insert a cur. Set pre to the node before the location where the cur is inserted and perform the following operations to complete the insertion of the cur:

last.next = cur.next
cur.next = pre.next
pre.next = cur
Copy the code

6. Set cur = last.next, where cur is the next element to be inserted.
7. Repeat steps 5 and 6 until cur becomes empty and the sort is complete.
8. Returns dummyHead.next, which is the head node of the sorted list.

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var insertionSortList = function(head) {
    if(! head){return head
    }
    const dummyHead = new ListNode(0)
    dummyHead.next = head

    let last = head, cur = head.next

    while(cur){
        if(last.val <= cur.val){
            last = last.next
        }else{
            let pre = dummyHead
            while(pre.next.val <= cur.val){
                pre = pre.next
            }
            last.next = cur.next
            cur.next = pre.next
            pre.next = cur
        }
        cur = last.next
    }
    return dummyHead.next
};
Copy the code

Complexity analysis:

• Time complexity: O(n), for a linked list, it is only necessary to update the pointer of adjacent nodes when inserting elements, so the time complexity of the insertion operation is O(1), but finding the insertion position requires traversing the nodes in the list, and the time complexity is O(n), so the total time complexity of the insertion sorting of the linked list is still O(n), where N is the length of the list.
• Space complexity: O(1), requires an additional constant size of auxiliary space.

(21) Odd-even linked list

Given a single linked list, put all the odd and even nodes together separately. Note that the odd and even nodes here refer to the parity of the node number, not the parity of the node’s value.

Try using the in-place algorithm. Your algorithm should have a space complexity of O(1) and a time complexity of O(Nodes), nodes being the total number of nodes.

Example 1:

Input:1->2->3->4->5- > NULL output:1->3->5->2->4->NULL
Copy the code

Example 2:

Input:2->1->3->5->6->4->7- > NULL output:2->3->6->7->1->5->4->NULL
Copy the code

Description:

• The relative order of odd and even nodes should be maintained.
• The first node of the list is treated as odd, the second as even, and so on.

All the elements in the list are divided into two lists, a and B, which are used to hold odd and even values, respectively. After the traversal, the even-numbered list is concatenated after the odd number list. The specific implementation process is as follows:

• First, the number of linked list nodes is 0,1,2, and the case is excluded, directly return head
• Two linked lists a and B are defined, representing odd and even nodes respectively. Node is used to temporarily store the head node of b linked list for convenience of subsequent concatenation
• The while loop is used to make cross-traversal assignments to lists A and B. A and B always point to the last node of the odd and even chains
• Concatenate the two lists and return

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var oddEvenList = function(head) {
    if(head === null || head.next === null || head.next.next === null) {return head
    }
    let a = head       // Store the odd number of nodes
    let b = head.next  // Store even-numbered nodes
    const node = head.next   // Record the head node of b list
    while(b ! = =null&& b.next ! = =null){
        a.next = b.next
        a = a.next
        b.next = a.next
        b = b.next
    }
    a.next = node
    return head
};
Copy the code

Complexity analysis:

• Time complexity: O(n). Among themnIs the length of the list, and we need to traverse the entire list.
• Space complexity: O(1). Additional constant size auxiliary space is required.