The 9 basic operations of the "Algorithms and Data Structures" list

preface

Linked lists in data structures are still very important, so this chapter makes a summary of relevant topics in offer and LeetCode and shares it with you 🤭

To tell you the truth, sometimes, want to express their ideas a little difficult, but also a rough man is not very good writing, some conceptual problems, or quote from other places to explain better, so I hope you understand.

For those unfamiliar with time and space complexity, check out the following article

How to understand the time complexity notation of algorithms, such as O(n²), O(n), O(1), O(nlogn), etc.?

Time and space complexity of the algorithm

Code word is not easy, to help you, like a support

Linked list topics will be added to GitHub, ideas and code are available, interested partners can play 👇

Data structures – Linked lists

List Linked List

A common basic data structure, also a linear table, does not store data in the order of a linear table. Instead, it stores Pointers on each node to the next node.

Linked lists can be O(1) inserted, much faster than sequential lists, another linear list, but it takes O(n) time to find a node or access a node with a specific number, whereas sequential lists are O(log n) and O(1) respectively.

The advantages and disadvantages:

❝

The linked list structure can overcome the disadvantage that the array linked list needs to know the data size in advance. The linked list structure can make full use of computer memory space and realize flexible memory dynamic management. However, linked lists lose the advantage of random array reading, and because of the increase of node pointer field, linked lists have a large space overhead.

❞

“Linked lists allow insertion and removal of nodes at any location on the table, but do not allow random access.“

There are many different types of linked lists:

Singly linked list
Two-way linked list
Circular linked list

Linked lists can often be derived from circular lists, static lists, double-linked lists, etc. For linked list use, care should be taken with the use of “headers”.

class ListNode {
            constructor(val) {
                this.val = val;
                this.next = null;
            }
 }  // Single list insert, delete, search  class LinkedList {  constructor(val) {  val = val === undefined ? 'head' : val;  this.head = new ListNode(val)  }   // return -1 if val is not found  findByVal(val) {  let current = this.head  while(current ! = =null&& current.val ! == val) { current = current.next  }  return current ? current : - 1  }   // Insert the node after the value val  insert(newVal, val) {  let current = this.findByVal(val)  if (current === - 1) return false  let newNode = new ListNode(newVal)  newNode.next = current.next  current.next = newNode  }   // Get the previous node of nodeVal, -1 if not found, val  // Applies to linked lists with no duplicate nodes  findNodePreByVal(nodeVal) {  let current = this.head;  while(current.next ! = =null&& current.next.val ! == nodeVal) current = current.next  returncurrent ! = =null ? current : - 1  }   // Find the current node by index  // Can be used to compare lists with duplicate nodes   findByIndex(index) {  let current = this.head,  pos = 1  while(current.next ! = =null&& pos ! == index) { current = current.next  pos++  }   return (current && pos === index) ? current : - 1  }   // Delete a node. If the deletion fails, return false  remove(nodeVal) {  if(nodeVal === 'head') return false  let needRemoveNode = this.findByVal(nodeVal)  if (needRemoveNode === - 1) return false  let preveNode = this.findNodePreByVal(nodeVal)   preveNode.next = needRemoveNode.next  }    // Iterate over the node   disPlay() {  let res = new Array(a) let current = this.head  while(current ! = =null) {  res.push(current.val)  current = current.next  }  return res  }   // Insert a new node at the end of the list  push(nodeVal) {  let current = this.head  let node = new ListNode(nodeVal)  while(current.next ! = =null)  current = current.next  current.next = node  }  // Insert in the header  frontPush(nodeVal) {  let newNode = new ListNode(nodeVal)  this.insert(nodeVal,'head')  }  } Copy the code

Of course, there may be some other methods that I haven’t thought of, and the rest can be done on my own

“Use of linked list classes“

  let demo = new LinkedList() // LinkedList {head: ListNode}
        // console.log((demo.disPlay())) 
        demo.push('1232')
        demo.insert(123.'head');
        demo.push('last value')
 demo.frontPush('start')  demo.remove('head')  // demo.remove('last value')  // console.log(demo.remove('head'))  // demo.push('2132')  // demo.insert(' nonexistent value ', 'failed to insert ') // return-1  console.log(demo.findByIndex(1))  console.log((demo.disPlay())) Copy the code

FindByIndex pos = 0 or pos = 1 (findByIndex pos = 0, findByIndex pos = 1) There is no exact standard for whether the remove function can remove the ‘head’ node.

Keep in mind that it’s not the only criteria, and if you think you can delete ‘head’, that’s fine.

“Two-way linked list“

Double-linked lists work in a similar way, but there is also a reference field called a “prev” field. With this extra field, you can know the previous node of the current node.

Let’s look at an example:

The green arrow shows how our “prev” field works.

“Structure similar to 👇“

class doubleLinkNode {
            constructor (val) {
                this.val = val
                this.prev = null
                this.next = null
 }  } Copy the code

Similar to a single-linked list, we will use a header to represent the entire list.

Insert and delete are a little more complicated than single-linked lists because we also need to deal with “prev” fields.

“Add operation – double linked list“

For example, of course, the best way to do this is to draw pictures.

Let’s add a new node 9 after the existing node 6:

Step 1: Link cur (9) to prev (6) and next (15)

Step 2: Relink prev (6) to Next (15) with cur (9)

“So when you do a list problem, the most important thing is to draw a picture, and when you draw a picture, the code comes out“

One question left is, what if we want to insert a new node at the beginning or at the end?

“Delete operation – double linked list“

For example, 👇

Our goal is to remove node 6 from the double-linked list

Therefore, we link its previous node 23 to its next node 15:

Node 6 is not in our double-linked list right now

Here’s a question: What if we want to delete the first node or the last node?

Drawing 🤭

Code will not write, a lot of online can code, you can see how others write

summary

Let’s briefly review the performance of singly and doubly linked lists.

They are similar in many operations

Both of them canDelete the first node in O(1) time.
Both of them canAdd a new node after the given node or at the beginning of the list in O(1) time.
None of them can be in constant timeRandom access data.

However, deleting a given node (including the last node) is slightly different.

In a singly linked list, it can’t get the previous node of a given node, so we have to spend before deleting a given nodeO(N)Time to find the previous node.
In double-linked lists, this is easier because we can retrieve the previous node using the “prev” reference field. So we can do it inO(1)Delete a given node in time.

Compare the time complexity of linked lists with other data structures (arrays, queues, stacks) :

After this comparison, we can easily come to the conclusion that:

❝

If you need to add or remove nodes frequently, linked lists can be a good choice.

If you often need to access elements by index, arrays may be a better choice than linked lists.

❞

Next is the focus of this article, from theory to practice, see what types of questions 👇

The basic topic

The following types of questions are sorted according to the order of individual questions, and the degree of difficulty will also be divided for your reference.

The main problem site is 👇

The sword refers to offer
Power button leetcode

Merge two ordered lists ⭐

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

❝

Link: [force link] merges two ordered lists

❞

“Example:“

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

Non-recursive thinking:

Simulation + linked list
Of course, the idea is simple, but the important thing is to simulate the process. In terms of algorithm, this kind of question can be compared with the simulation question, which can simulate the process of your thinking. Each time, compare the size of two L1. val and l2.val, take the smaller value, and update the smaller value to point to the next node
The main thing to notice is the loop termination condition: when either of them is null, it points to null
Finally, we need to determine which of the two linked lists is not empty, and then connect the non-empty list to the TMP sentinel node.

  var mergeTwoLists = function (l1, l2) {
            let newNode = new ListNode('start'),  // Head node
                tmp = newNode;    // TMP serves as the sentinel node
            while (l1 && l2) {   // The loop ends with the condition that both are non-null
                if(l1.val >= l2.val) {
 tmp.next = l2  l2 = l2.next  }else{  tmp.next = l1  l1 = l1.next  }  tmp = tmp.next // Sentinel node updates point to the next node  }  // Finally, we need to determine which list still has non-null  tmp.next = l1 == null ? l2 : l1;  return newNode.next;  }; Copy the code

Recursive thinking: “Recursive solution should pay attention to the recursion topic each time the return value of the node, so as to ensure that we end up with a list of the smallest start.”

The initial approach is to simulate + linked lists, but when you see recursion in the discussion area, it’s definitely a good idea to look at it. Multiple solutions to a problem is still very important, which also diverges thinking to some extent, or advocate multiple solutions.

Recursive exit: When any list is empty, return another link directly, that is, the concatenation process
Compare the nodes from the two lists, and the smaller one is picked as the next list node

The code point here is ☑️

Returns the penultimate KTH node ⭐

Implement an algorithm to find the penultimate KTH node in a one-way linked list. Returns the value of this object.

❝

Link: [force link] returns the penultimate KTH node

❞

The two-pointer notation 👇

Let’s get two Pointers before and after, let the last pointer go k, then the two Pointers differ by k, and then we iterate over the last pointer, and when the last pointer is null, the first pointer is the answer, because they started out k apart

The code point here is ☑️

Reverse linked lists ⭐

Reverse a single linked list.

❝

Link: [leetcode] inverts a linked list

❞

“Example:“

Input: 1 - > 2 - > 3 - > 4 - > 5 - > NULLOutput: 5 - > 4 - > 2 - > 3 - > 1 - > NULLCopy the code

Prev curr next iterates through three prev curr next Pointers

Each time the current curr pointer points to the previous pre
Next Saves information about the next node

Tip: Initially set the sentinel node to NULL and the curr to head

Keep iterating down to know that the current node of CURr is the last node

        var reverseList = function (head) {
            if(! head)return null
            let prev = null.                curr = head
            while( curr ! =null) {
 let next = curr.next;  curr.next = prev  prev = curr  curr = next  }  return prev  }; Copy the code

Recursive writing

We talked about the idea before, so let’s look at the code

var reverseList = function(head) {
    let reverse = (prev,curr) = > {
        if(! curr)return prev;
        let next = curr.next;
        curr.next = prev;
 return reverse(curr,next);  }  return reverse(null,head); };  Copy the code

The code point here is ☑️

Interval reversal ⭐⭐

Reverse the linked list from position m to n. Use a scan to complete the inversion.

Description: 1 ≤ m ≤ n ≤ Length of the linked list.

❝

Link: [Leetcode] Reverse linked list II

❞

“Example:“

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

Same thing as the last problem, so we can still do it iteratively.

Two nodes,tail and front, need to be recorded

The purpose of the two nodes is to rejoin into a new linked list after the final interval inversion.

var reverseBetween = function (head, m, n) {
            let count = n-m,
                newNode = new ListNode('head');
            tmp = newNode;
            tmp.next = head;              // Sentry node, which also ensures that the next node to newNode is head
 for(let i = 0; i < m - 1; i++ ){  tmp = tmp.next;  }  // After this loop, TMP retains the previous node in the inversion range, so use front to preserve it  let front, prev, curr,tail;  front = tmp; // save the first node of the interval  // At the same time, the tail pointer is used to link the inverted node to the last node   prev = tail = tmp.next; // Preserve the tail node of the queue after the inversion  curr = prev.next  for(let i = 0; i < count; i++ ) {  let next = curr.next;  curr.next = prev;  prev = curr  curr = next  }  // link the first node of the interval to the last node  tail.next = curr  // font is the first node of the interval, and the last node of the interval inversion needs to be linked  front.next = prev   return newNode.next // Just return newNode.next. We started with the head node   }; Copy the code

Click here at 🤭

Switch nodes in the linked list in pairs ⭐⭐

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

❝

Link: Leetcode switches nodes in a linked list in pairs

❞

“Example:“

Given 1->2->3->4, you should return 2->1->4->3.Copy the code

Iterating ideas, routines, add a TMP sentinel node on the line. If you still don’t understand, draw a picture to solve everything. If you really don’t understand, look at this picture

 var swapPairs = function (head) {
        let newNode = new ListNode('start');
            newNode.next = head,    // link header node routine operation
            tmp = newNode;          // TMP sentry node, which starts with newNode, not head

 while( tmp.next ! = =null&& tmp.next.next ! = =null) {  let start = tmp.next,  end = start.next;  tmp.next = end  start.next = end.next  end.next = start  tmp = start  }   return newNode.next // Return the next pointer to the first node of the list  }; Copy the code

Of course, really write when the interview, drawing should be possible, looking at the figure to write, easy, really, I recursive method ✍ can’t come out, I good stupid 🤭

The code point here is ☑️

A group of K flip linked lists ⭐⭐⭐

Given a linked list, each k nodes in a group of flipped, please return to the flipped list.

Description: 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, keep the last remaining nodes in the same order.

❝

Links: [a group of K flipped lists](https://leetcode-cn.com/problems/swap-nodes-in-pairs/)

❞

Example:

Given the linked list: 1->2->3->4->5When k = 2, it should return: 2->1->4->3->5When k = 3, it should return: 3->2->1->4->5Copy the code

First look at the problem solution,leetcode⭐⭐⭐ problem, do not need to waste time to think, you can look at others’ ideas, understand others’ ideas, and finally convert to their own ideas is very important. After reading really Epiphany, know how to achieve.

Because we have k groups, we have to have a count to count the number of nodes.
startThat’s what the pointer meansstartThe recorded information is the node preceding the start node location of the current grouping.
endThe pointer represents the next node to be flipped.
In turn,startPoint to the flipped list, interval(Start, end)Returns the last node instartNode.
In this case, the last node in the flipped group also needs to point to the next group, i.efront.next = cur
So the node with the value of 1 points to end

For example, head=[1,2,3,4,5,6,7,8], k = 3

If you can’t see it, draw a picture and read it several times in combination with the code. The problem will be seen and written several times, and you will feel it naturally.

“Critical point analysis“

Create a newNode
Group the linked list in k units, recording the start and end node positions of each group
Flip each group accordingly, remembering to change positions
Returns the newNode. Next

  var reverseKGroup = (head, k) = > {
            
            let  reverseList = (start, end) = > {
                let [pre, cur] = [start, start.next],
                    front = cur;
 // The terminating condition is that the current node cannot equal the end node   // Reverse routines  while( cur ! == end) { let next = cur.next  cur.next = pre  pre = cur  cur = next  }  front.next = end // The new flipped list needs to be joined, i.e. front points to a node after the original range  start.next = pre // The start of the new flip needs to be connected to start.next  return front // return the list to be joined after the flip  }   let newNode = new ListNode('start')  newNode.next = head;  let [start, end] = [newNode,newNode.next],  count = 0;  while(end ! = =null ) {  count++  if( count % k === 0) {  // after k nodes are flipped, the return value is the one before end  start = reverseList(start, end.next)  end = start.next  }else{  // A grouping does not point to the next node  end = end.next  }  }  return newNode.next  }; Copy the code

Good guy, interview of time, want me to write this, don’t let me draw a picture of words, I abstract not to come out 💢💢

The code point here is 🤭

Merge K sorted linked lists ⭐⭐⭐

Merge k sorted linked lists and return the merged sorted linked lists. Analyze and describe the complexity of the algorithm.

❝

Link: [Merge K sorted linked lists](https://leetcode-cn.com/problems/swap-nodes-in-pairs/)

❞

“Example:“

Input:[
1 - > 4 - > 5,1 - > 3 - > 4,2 - > 6] Output: 1 - > 1 - > 2 - > 3 - > 4 - > 4 - > 5 - > 6Copy the code

[Palindrome linked list]⭐

Please determine whether a linked list is a palindrome linked list.

❝

Link: Leetcode – Palindrome linked list

❞

“Example:“

Input:[
1 - > 4 - > 5,1 - > 3 - > 4,2 - > 6] Output: 1 - > 1 - > 2 - > 3 - > 4 - > 4 - > 5 - > 6Copy the code

“Example 1:“

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

“Example 2:“

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

Answer:

Find the middle point of the list, then reverse the bottom half, and you can compare the results in turn.

The key is how do you find the midpoint?

“How fast a pointer“

Set a middle pointer mid. In a traversal, head goes two squares and mid goes one. When head reaches the last value or jumps out, mid points to the middle value.

let mid = head
// Loop condition: at least once as long as head existswhile(head ! == null && head.next ! == null) {Head = head.next. Next // The pointer moves two squares at a timeMid = mid. Next // The middle pointer moves one space at a time} Copy the code

When iterating, the linked list is reversed by iteration. All nodes before mid are reversed. Use iteration to reverse.

while(head ! == null && head.next ! == null) {        pre = mid
        mid = mid.next
        head = head.next.next
        pre.next = reversed
 reversed = pre  } Copy the code

Such as:

Odd number: 1 -> 2 -> 3 -> 2 ->1After traversal, mid = 3->2->1reversed = 2->1
Copy the code

Even: 1 -> 2 -> 2 ->1After traversal is complete: mid = 2->1reversed = 2->1
Copy the code

Complete code:

  var isPalindrome = function (head) {
            if (head === null || head.next === null) return true;
            let mid = head,
                pre = null.                reversed = null; // reversed the reversed linked list
  while(head ! = =null&& head.next ! = =null) {  // A normal flip routine  pre = mid  mid = mid.next  head = head.next.next  pre.next = reversed  reversed = pre  }  // If the number of linked lists is odd, mid goes back one bit  if (head) mid = mid.next  while (mid) {  if(reversed.val ! == mid.val)return false  reversed = reversed.next  mid = mid.next  }  return true  }; Copy the code

[Linked list intersection]⭐

Given two (one-way) linked lists, determine whether they intersect and return the point of intersection. Note that the definition of the intersection is based on the reference to the node, not the value of the node. In other words, if the KTH node of one list is the same node (identical references) as the JTH node of another list, then the two lists intersect.

❝

Link: [Leetcode – Linked list intersection]

❞

Example 1:

Enter: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3Output: Reference of the node with value = 8Input explanation: The value of the intersection node is 8 (note that it cannot be 0 if two lists intersect). Starting from their respective table headers, linked list A is [4,1,8,4,5] and linked list B is [5,0,1,8,4,5]. In A, there are two nodes before the intersecting node; In B, there are three nodes before the intersection node.Copy the code

Example 2:

Enter: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1Output: Reference of the node with value = 2Input explanation: The value of the intersection node is 2 (note that it cannot be 0 if two lists intersect). Starting from their respective table headers, linked list A is [0,9,1,2,4] and linked list B is [3,2,4]. In A, there are three nodes before the intersecting node; In B, there is 1 node before the intersecting node.Copy the code

Example 3:

Enter: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2Output: nullInput explanation: from the respective table headers, linked list A is [2,6,4] and linked list B is [1,5]. Because the two linked lists do not intersect, intersectVal must be 0, and skipA and skipB can be arbitrary values.Explanation: The two lists do not intersect, so null is returned.Copy the code

Ideas:

Set two Pointers. After each pointer has finished its path, it points to another linked list. If two nodes are equal, they must be the same point.
Because they’re going the same distance, and they’re going 1 each time, they’re going the same distance, they’re going at the same speed, and if they’re equal, they must be the same point.

var getIntersectionNode = function (headA, headB) {
    let p1 = headA,
        p2 = headB;
    while(p1 ! = p2) {        p1 = p1 === null ? headB : p1.next
 p2 = p2 === null ? headA : p2.next  }  return p1 }; Copy the code

The code point here is 🤭

The topic

Choose a part of the topic out, I hope you can be a process of it, is also a summary of the self, the next will continue to brush the topic, need to continue to brush with me, you can see the following oh 👇

Making here

❤️ thank you

If you find this article helpful:

Click “like” to support it, so that more people can see this content.
Share your thoughts with me in the comments section, and record your thought process in the comments section.
If you feel good, you can also check out the previous article:

[full of sincerity 👍]Chrome DevTools debugging tips, efficiency ➡️🚀🚀 ➡️

[practical 👍] Recommend some great front-end sites

[Dry goods 👍] From detailed manipulation of JS arrays to an analysis of array.js in V8

[1.2w word 👍] To his girlfriend’s secret – how the browser works (on)

[1.1W word] To his girlfriend’s secret – how the browser works (rendering process) chapter

[suggestion 👍] Again 100 JS output questions sour cool continue (total 1.8W words + consolidate JS foundation)

✍ take you to fill some JS error prone pits

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

The 9 basic operations of the “Algorithms and Data Structures” list

preface

List Linked List

summary

The basic topic

Merge two ordered lists ⭐

Returns the penultimate KTH node ⭐

Reverse linked lists ⭐

Interval reversal ⭐⭐

Switch nodes in the linked list in pairs ⭐⭐

A group of K flip linked lists ⭐⭐⭐

Merge K sorted linked lists ⭐⭐⭐

[Palindrome linked list]⭐

[Linked list intersection]⭐

The topic

❤️ thank you

The 9 basic operations of the “Algorithms and Data Structures” list

preface

List Linked List

summary

The basic topic

Merge two ordered lists ⭐

Returns the penultimate KTH node ⭐

Reverse linked lists ⭐

Interval reversal ⭐⭐

Switch nodes in the linked list in pairs ⭐⭐

A group of K flip linked lists ⭐⭐⭐

Merge K sorted linked lists ⭐⭐⭐

[Palindrome linked list]⭐

[Linked list intersection]⭐

The topic

❤️ thank you

Related Posts

Front-end error monitoring – a combination of Vue and Sentry

14 Habits of Being an Effective Programmer (Part 1)

inheritance