First published at: github.com/USTB-musion…

Writing in the front

Today we’ll talk about two very basic data structures in front-end interviews — “arrays” and “linked lists.”

Here are some common interview questions:

  1. Talk about the difference between linked lists and arrays
  2. How do I reverse a one-way linked list
  3. Find three numbers in the array such that their sum is N
  4. Given a linked list, how to delete the penultimate NTH node of the list

You can think about how to answer the above question 🤔 and then read the rest with the answer in mind.

1. The difference between linked lists and arrays

Before we talk about that, let’s look at the logical structure of the data. There are two main types: linear tables and nonlinear tables.

Linear list: a structure in which data is connected into a line, such as linked lists and arrays, stacks, queues, etc.

Nonlinear table: The relationship between data is nonlinear, such as tree, heap, graph, etc.

After looking at linear tables and nonlinear tables, let’s continue:

Array definition: Data is a linear table data structure that uses a contiguous memory space to store a group of data of the same type.

Since arrays are contiguous in memory, it is very efficient to randomly access the elements of an array by subscript. But at the same time, to ensure continuity, if you want to add an element to the array, you need to move the data around a lot. The same is true for removing an element from an array. So we conclude that random access to an array is efficient, but adding and removing is inefficient, with an average time complexity of O(n).

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.

I just showed you that adding and removing an element from an array is inefficient. The storage space of linked lists is discontinuous. To add or delete data in linked lists, we do not need to move data in order to maintain the continuity of memory, so it is very efficient to add and remove elements in linked lists. However, every coin has two sides. Because the storage space of a linked list is discontinuous, when you want to access an element in a linked list, you cannot calculate the corresponding node according to the initial address and subscript through the addressing formula like an array. You can only find the corresponding node by iterating through the pointer. So we conclude that adding and removing operations in linked lists is very efficient, while random access is very inefficient, with an average time complexity of O(n).

Through the introduction of the previous content, a table is used to visually see the difference of time complexity between the two types:

Time complexity An array of The list
add O(n) O(1)
delete O(n) O(1)
Random access O(1) O(n)

So here’s the difference between lists and arrays:

1. The memory is organized differently

2. The time complexity of adding, deleting, and inserting varies

3. The linked list supports dynamic expansion

2. How to reverse a one-way linked list

Example:

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

Set three variables to represent the current node and the nodes before and after the current node.

var reverseList = function(head) { let pre = null; for (let cur = head; cur;) { let nextTemp = cur.next; // Save the next node of the current head node cur.next = pre; pre = cur; cur = nextTemp; } return pre; };Copy the code

3. Find three numbers in the array whose sum is N

Given an array nums containing n integers, determine whether there are three elements a, B, and c in nums such that a + b + c = 0. Find all the triples that meet the criteria and are not duplicated.

For example, a given array nums = [1, 0, 1, 2, 1, 4], meet the requirements of the ternary group collection: [[- 1, 0, 1], [1, 1, 2]]Copy the code

1. Sort the array. If the first element of the array is greater than 0 or the last element is less than 0, then the sum cannot be 0;

2. First select an element (A), and then use A double pointer to traverse the elements of the array. One pointer points to the last element (B) of element A, and the other pointer points to the last element (C) of the array.

3. Determine whether the result of B+C is the negative of A. If B+C > (-a), make the pointer of C move forward; if B+C <(-a), make the pointer of B move backward;

4. If the element of the pointer B is equal to the element before it, the pointer B moves back one bit. If the C pointer is equal to the following element, the C pointer moves forward one bit;

5. Repeat the preceding steps

The implementation code is as follows:

Var threeSum = function(nums) {let result = new Array(); // let head; // let end; // let fixedVal; // sort nums.sort((a, b) => {return a-b; }); / / determine whether array element as an integer or a negative number, direct return if (nums [0] > 0 | | nums [nums. Length - 1] < 0) return the result; // start traversing for (let I = 0; i < nums.length; I ++) {// fixedVal = nums[I]; If (fixedVal === nums[i-1]) continue; if(fixedVal === nums[i-1]) continue; // the initial fixed value is nums[0], so the head pointer is I +1; // End = nums.length - 1; While (head < end){if(nums[head] + nums[end] + fixedVal === 0){ Let group = new Array(); group.push(nums[head]); group.push(nums[end]); group.push(fixedVal); result.push(group); // Head += 1; // Head += 1; end -= 1; While (head < end && nums[head] === nums[head-1]){head += 1; While (head < end && nums[end] === nums[end + 1]){end -= 1; }else if(nums[head] + nums[end] + fixedVal < 0){head++; }else{// Otherwise, the tail pointer moves forward so that the data is less than the metadata end--; } } } return result; };Copy the code

4. Given a linked list, how to delete the NTH node from the penultimate of the list

Given a linked list, delete the NTH last node of the list and return the first 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 becomes 1->2->3->5.Copy the code

We can use two Pointers instead of one. The first pointer moves n+1 step forward from the beginning of the list, while the second pointer starts at the beginning of the list. Now, these two Pointers are separated by n nodes. We keep this constant interval by moving both Pointers forward at the same time until the first pointer reaches the last node. The second pointer points to the NTH node from the last node. We relink the next pointer to the node referenced by the second pointer to the node next to that node.

var removeNthFromEnd = function(head, n) { let first = head; For (let I = 0; i < n; i++) { first = first.next; } if (! first) return head.next; // delete first node let second = head; While (first.next) {first = first.next; second = second.next; } second.next = second.next.next; return head; };Copy the code

The resources

leetcode

You can pay attention to my public account “Muchen classmates”, goose factory code farmers, usually record some trivial bits, technology, life, perception, grow together.