The concept of linked lists
According to the encyclopedia:
A linked list is a non-sequential storage structure on a physical storage unit. The logical order of data elements is realized by linking the order of Pointers in the linked list.
It looks something like this:
There are many types of linked lists, such as unidirectional linked lists, bidirectional linked lists, circular linked lists, block linked lists and so on. This article will only involve unidirectional, bidirectional and circular lists.
Linked lists sometimes look at the code will not be very easy to understand, it is recommended to learn at the same time drawing pictures on draft paper can help understand.
Singly linked list
According to the encyclopedia:
The simplest type of linked list is a one-way linked list, which contains two fields, an information field and a pointer field. The link points to the next node in the list, and the last node points to a null value.
The nodes of a one-way linked list are divided into two parts. The first section stores or displays information about the node, and the second section stores the address of the next node. A one-way linked list can only traverse in one direction.
Here are a few nouns to know:
Header: The first node of a singly linked list
Endnode: The last node of a singly linked list
Current node: The currently pointed node held by an intermediate variable used to traverse the list
Sentinel node (or dummy node) : a node that has no practical purpose and is used to facilitate operation when performing linked list operations
Define a one-way linked list node
Since a linked list is made up of nodes, we can define the nodes of the list using the constructor or class:
// The function is defined in the same way as leecode
function ListNode(val, next) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
/ / the class definition
class ListNode {
constructor(val, next) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null: next; }}/ / use
let list = new ListNode(1);
// Add a node after the list
list.next = new ListNode(2);
{val: 1, next: {val: 2, next: null}}
Copy the codeCreate a one-way linked list
With the constructor of the linked list node, we need to prepare a linked list in advance for the convenience of learning the algorithm of the linked list. There are two methods to create the linked list, namely the head interpolation method and the tail interpolation method.
To facilitate the random generation of numbers, use a utility function
// generate a random number in the range [0, 100]
function generateNumber() {
return Math.floor(Math.random() * 101);
}
Copy the codeCreating linked lists: Header interpolation
Header interpolation, as the name implies, is the method of inserting nodes at the head of the linked list, so that the linked list is in reverse order.
/** * create a list of random lengths and return the head node. This method requires a dummy node to help * h -> N(N) ->... -> N(2) -> N(1) * * * * * * * * * * * * * * * * * * * *
function createListFromHead() {
// List length
let len = generateNumber();
console.log("Create a value of length :", len, "Linked list");
// Create a header. This header will be used as a dummy
let head = new ListNode(-1);
while (len > 0) {
let newNode = new ListNode(generateNumber());
// h -> N(n) -> ... -> N(2) -> N(1)
// Insert a new node after the header
// select * from 'head' where 'head'; 2. Place the new node after the head node.
newNode.next = head.next;
head.next = newNode;
len--;
}
// the dummy node needs to be removed on return
return head.next;
}
Copy the codeCreating linked lists: Tail interpolation
Tail insertion, as the name implies, is the method of inserting nodes at the end of the list, so that the list is positive order.
/** * create a list of random length, and return the head node * N1 -> N2 ->... -> Nn * implementation: add nodes from beginning to end, so it is in order, also called tail insert method */
function createListFromTail() {
// List length
let len = generateNumber();
console.log("Create a value of length :", len, "Linked list");
// Set a head variable to hold the head
let head = null;
// Set a end node, which will always be used as a end node, as a temporary node
let end = null;
while (len > 0) {
let newNode = new ListNode(generateNumber());
// The initial head and tail are the same
if (head === null) {
head = newNode;
end = head;
} else {
// add new node to end node;
end.next = newNode;
// 2. After assigning newNode to end, the next loop to 1 will be the same as newNode.next
// The reference continues from the beginning node to the end node.
// For simplicity, think of it as moving the end pointer to a new node.
end = newNode;
}
len--;
}
return head;
}
Copy the codeInsert a node into the linked list
The above two methods are suitable for creating a linked list quickly. They are not used very much in practice, and are more about inserting a node into a linked list.
When you want to insert a node into a linked list, you need to know where you want to insert it, and if you don’t know where you want to insert it, then you have to find where you want to insert it, for example, by searching for where a node is in the linked list, which we’ll talk about later.
/** * inserts a node * to the specified position in the singly linked list@param {*} Head the list *@param {*} NewNode Specifies the node * to be inserted@param {*} Index The position to insert, with subscripts starting at 0 */
function insert(head, newNode, index) {
// If it is an empty list, assign the new node to the empty list
if (head === null) {
// An empty list can only be inserted from position 0, otherwise the list is returned without any processing
if(index ! = =0) {
return head;
}
head = newNode;
return head;
}
// Insert nodes into the list header
if (index === 0) {
// This swap operation is almost standard for linked lists
// Point the new node to the head node, which makes the chain with the new node as the head
newNode.next = head;
// Change the header node to a new one
head = newNode;
return head;
}
// Insert logic at other locations
// currentNode is almost a standard part of the list
let currentNode = head;
// Set currentNode position
let count = 0;
// Start from the start node to find the target location, to find the target node before the node
while(currentNode.next ! = =null && count < index - 1) {
currentNode = currentNode.next;
count++;
}
// Now count and currentNode are in the first digit of the target node
if (count === index - 1) {
// Add a pointer to the target node (currentNode is the first bit of the target node, so currentNode.next points to the target node)
newNode.next = currentNode.next;
// Insert the pointer to the new node
currentNode.next = newNode;
}
return head;
}
Copy the codeThis insertion method is based on the fact that the header is not a dummy node. If your header has a dummy node, the above code will need to be modified.
Now that we have the insert method, we can create lists using this method.
Create linked lists using the INSERT method
/ / an empty list
let head = null;
for (let i = 0; i < 100; i++) {
const newNode = new ListNode(i + 1);
head = insert(head, newNode, i);
}
// Head is a list of 100 nodes
Copy the codeTraversing the list
So now that we have a linked list, how do we go through the list and print out the data at every node?
/** * Prints the list, traversing all nodes in the list from the incoming header *@param {*} Head linked list, no dummy */
function printList(head) {
// See, Karent? Nude came to help again, and Hyde stepped aside to rest
let currentNode = head;
const result = [];
while(currentNode ! = =null) {
result.push(currentNode.val);
// To iterate through the list is to move currentNode back and forth
currentNode = currentNode.next;
}
console.log("There are all linked lists.", result.length, "A node"."Results are :");
console.log(result);
}
Copy the codeNow that we know how to walk through the list, let’s look for some node in the list.
Find a node in a linked list
First, do a simple search for the node where the specified value resides
/** * Finds the node of the specified value in the singly linked list and returns it *@param {*} Head single linked list *@param {*} Val is the value to look for *@returns Returns the linked list */ with the target node as its head
function searchNode(head, val) {
let currentNode = head;
while(currentNode ! = =null&& currentNode.val ! == val) { currentNode = currentNode.next; }return currentNode;
}
Copy the codeMake it a little harder, find the node where the value is, and see where it is
/** * Finds the node * in a single linked list@param {*} Head single linked list *@param {*} Val is the value to look for *@returns If not found, return -1. If found, return 0
function searchPosition(head, val) {
let currentNode = head;
// To find a location, you need to use a counter
let count = 0;
while(currentNode ! = =null&& currentNode.val ! == val) { currentNode = currentNode.next; count++; }if (currentNode === null) {
return -1;
}
return count;
}
Copy the codeAnother way, suppose we know where the node is, but we don’t know what the node is. This is also easy:
function searchNode(head, index) {
let currentNode = head;
let count = 0;
while (count < index) {
currentNode = currentNode.next;
count++;
}
return currentNode;
}
Copy the codeCome on, you’re almost done learning how to delete nodes from a linked list.
Delete a node in the linked list
There are two ways to delete a node: one is to know the location to be deleted, and the other is to know the value of the node (the value in the node is different).
The next one is to delete a node knowing where to delete it, and the other one is more or less the same.
/** * removes a node * at the specified position in the singly linked list@param {*} Head list (no dummy nodes) *@param {*} Index The position to delete, counting from 0 *@returns ListNode* /
export function deleteByPosition(head, index) {
if (head === null) return head;
if (index === 0) {
head = head.next;
return head;
}
// Think back to the insertion of nodes. Kant is useful
// This step changes currentNode to the previous node of the node to be deleted
let count = 0;
let currentNode = head;
while(currentNode.next ! = =null && count < index - 1) {
currentNode = currentNode.next;
count++;
}
CurrentNode. Next points to the node to be deleted
if (count === index - 1&& currentNode.next ! = =null) {
// Find the node to delete
let deletedNode = currentNode.next;
// add the pointer to the currentNode next to the deleted bit
currentNode.next = deletedNode.next;
// Free the memory of the isolated template node (js does not do this, because the automatic gc)
deletedNode = null;
}
return head;
}
Copy the codesummary
We have now covered the data structure of linked lists and some of the most basic algorithms: creating lists, inserting, traversing, finding, and deleting.
The following content will be based on the above basic algorithm to further deepen the difficulty of the problem, let’s learn how to solve these problems.
Flip single linked lists
To flip A list, you need to change the direction of the nodes in the list to the opposite direction. For example, if the original list was: A -> B -> C -> D -> NULL, it will become: D -> C -> B -> A -> NULL
/** * flip a single list, generally flip a list in place, no extra storage *@param {*} head* /
export function reverseSingleList(head) {
if (head === null) return head;
CurrentNode is now the head node
let currentNode = head.next;
head.next = null;
// Use a variable to hold the next node (as opposed to currentNode)
let nextNode = null;
// If you're plotting, you'll see that head, currentNode, and nextNode are a whole right-shift process, flipping the list as you go
// If the current traversal node is null, the rollover is complete
while(currentNode ! = =null) {
nextNode = currentNode.next;
// Set the current node pointer to head so that the first and second nodes are reversed.
NextNode is the lead node, and the rest of the chain has not been flipped.
// The other is the flipped chain where head and currentNode are
currentNode.next = head;
// Then Karent. Nude declared his job done and gave Hyde back his place as the boss
head = currentNode;
// Then Karent. It's not easy for Nude to run the other side and keep doing thingscurrentNode = nextNode; }}Copy the codeLinked list central detection
One problem is described this way:
Given A linked list (A -> B -> C -> D -> E -> B), how do you check if the list is looped?
More specifically: A -> B -> C -> D -> E -> A, that is, the tail points to the head, and the list forms A circular list.
To this question, some students will answer by saying: I walk through the list and store the value of the list in a temporary variable. If the current value is equal to the value of the temporary variable when I walk through the list, I have a ring. That’s a good idea, but it’s not the best way.
To solve this problem, you can use the way to run laps in the playground to solve, two students at the same time run in a direction, one of them run fast, the other one runs slowly, if the fast students catch up with the slow students, it shows that the playground is circular.
function hasCycle(head) {
// Two students run at the same time
let fast = head;
let slow = head;
// Since the fast student has to run two steps at a time, if the list is loopless, then the termination condition has two cases:
Next === null, there is no loop
// If the loop is in the penultimate position, then the loop is null
while(fast ! = =null&& fast.next ! = =null) {
// Fast students run two steps at a time
fast = fast.next.next;
// Slow students run one step at a time
slow = slow.next;
// This is not a value, but a pointer
if (fast === slow) {
return true; }}return false;
}
Copy the codeMerges two ordered lists
You have two incrementally sorted lists, and now you need to merge them so that the nodes in the new list are still incrementally sorted.
For example, given two linked lists:
L1: 1->2->4
L2: 1->3->4
After the merge, return: 1->1->2->3->4->4
/** * merge two ordered lists *@param {ListNode} L1
* @param {ListNode} L2
* @return {ListNode}* /
function mergeTwoLists(l1, l2) {
// We still use two variables to represent the nodes currently traversed
let curL1 = l1;
let curL2 = l2;
// It would be easier to use a dummy node as the head for this problem
let head = new SingleListNode(-1);
// Use a temporary pointer to continuously add nodes to the end of a linked list
// h -> N1 -> N2 -> ...
/ / write [end]
let end = head;
// If a chain is not empty, the loop must be re-entered to execute the logic inside
while(curL1 ! = =null|| curL2 ! = =null) {
// When l1 is finished, place the rest of L2 behind the main chain
if (curL1 === null) {
end.next = curL2;
return head.next;
// When L2 is finished, place all remaining l1 nodes behind the main chain
} else if (curL2 === null) {
end.next = curL1;
return head.next;
} else if (curL1.val < curL2.val) {
// Add nodes using tail Pointers
end.next = curL1;
// Move the tail pointer backwards
end = end.next;
/ / traverse
curL1 = curL1.next;
} else{ end.next = curL2; end = end.next; curL2 = curL2.next; }}}Copy the codeDelete the NTH node from the penultimate list
Given A linked list: A -> B -> C -> D -> E -> NULL enter 2 to delete the next-to-last node of the list where D is located. Result: A -> B -> C -> E -> NULL
The easiest way to do that is to go through the list and get the length, and then the length -n is the node that you want to delete, and then delete it.
But this requires two traversal operations, so we can optimize the solution by thinking like this:
Two students are running 100 meters on the playground. Assuming that the speed of A and B is the same, B starts to run when A runs 50 meters, and B just runs 50 meters when A reaches the finish line. And this 50 meter point is the node that we want to delete.
This idea is also used to solve the linked list has a ring, we used to call this idea called: fast or slow pointer. Some are called the hare and the tortoise.
/** * remove the NTH node from the list, and use dummy nodes to simplify the logic *@param {ListNode} head
* @param {number} n
* @return {ListNode}* /
function removeNthFromEnd(head, n) {
if (head === null || n <= 0) return head;
// Add a dummy node to the header. The main purpose is to help solve the problem of deleting the first node which happens to be the first node
let dummy = new ListNode(-1);
dummy.next = head;
// Set the speed pointer
let fast = dummy;
let slow = dummy;
let count = 0;
// Let the fast pointer traverse the first n nodes
while(fast.next ! = =null && count < n) {
fast = fast.next;
count++;
}
// When the fast pointer traverses the last node,
// The slow pointer traverses just before the node to be deleted
while(fast.next ! = =null) {
fast = fast.next;
slow = slow.next;
}
let deletedNode = slow.next;
slow.next = deletedNode.next;
deletedNode = null;
// No dummy nodes are required for return
return dummy.next;
}
Copy the codeFind the intermediate node of the linked list
It’s also easy to think twice, but using a fast or slow pointer is better.
/ * * *@param {ListNode} head
* @return {ListNode}* /
function middleNode(head) {
let fast = head;
let slow = head;
while(fast ! = =null&& fast.next ! = =null) {
// The fast pointer moves two Spaces at a time, the slow pointer moves one space at a time
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
Copy the codeTwo-way linked list
The basic algorithm is similar to a single linked list, but with one more precursor.
/** * A function that constructs a bidirectional list *@param {*} val Number
* @param {*} prior DoubleListNode
* @param {*} next DoubleListNode
*/
function DoubleListNode(val, prior, next) {
this.val = val === undefined ? 0 : val;
this.prior = prior === undefined ? null : prior;
this.next = next === undefined ? null : next;
}
Copy the codeCircular linked list
A singly linked list is a circular list when the tail pointer points to the head pointer.
A bidirectional list is one where the tail pointer points to the head and the head pointer points to the tail.
I won’t take you to do the specific bidirectional and circular linked lists, but if you are interested, you can go and do it.