This is the third day of my participation in Gwen Challenge

The list

The basic operations of linked lists

Through the learning of algorithms and data structures, we know what a linked list is, as well as some basic features of linked lists, val, next, etc., so today we will have a good study, what are the basic operations of linked lists!

Merge linked lists

First of all, how are we to know the list of merger, chain table she is ordered, also is to know yourself the next node pointed to where, if say we merge the two list, actually very easy, as long as the first list of the last node of the next point to the head of the second list node can, so how to merge two order list? Let’s look at the following topic 👇 :

Merges two ordered lists into a new ordered list and returns. A new list is formed by concatenating all the nodes of a given two lists. For example: input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4

First we explicitly, after the two list and output of the new list is ordered, so our thinking is how they strung together, at this point we can imagine the new list is now only a needle, and then from an existing list node to orderly strung together, you can get what we want list, no husband, not to, Let’s take a look at the picture below to understand:

From the above we can understand that it is actually a ratio of the size, we use the code to implement the merge list:

// Use the object form to simulate the ordered list, which can be more intuitive
const l1 = {
    val: 1.next: {
      val: 2.next: {
        val: 3.next: {
          val: 4.next: null}}}}const l2 = {
    val: 2.next: {
      val: 3.next: {
        val: 4.next: {
          val: 5.next: {
            val: 6.next: null
          }
        }
      }
    }
}
// Create a class for the list that returns our last list
class ListNode {
    constructor(val) {
      this.val = val
      this.next = null}}const mergeTwoLists = function (l1, l2) {
// Define a header to ensure that the list can be accessed
let head = new ListNode();
// cur Here is our needle
let cur = head;
console.log(head === cur); // It is a reference type because it is an instantiation of a class, so it is congruent
console.log(111,  head, cur, l1, l2); // 111 ListNode {val: undefined, next: null}next: {val: 1, next: {... }}val: undefined__proto__: Object ListNode {val: undefined, next: null}next: {val: 1, next: {... }}val: undefined__proto__: Object {val: 1, next: {... }}next: {val: 2, next: {... }}val: 1__proto__: Object {val: 2, next: {... }}
// The needle starts to move between L1 and L2
while (l1 && l2) {
  // if l1 has a smaller node value
  if (l1.val <= l2.val) {
    // start with l1
    cur.next = l1;
    // The L1 pointer moves forward
    l1 = l1.next;
  } else {
    // if l2 is small, string l2
    cur.next = l2;
    // l2 step forward
    l2 = l2.next;
  }

  // The "pin" also moves forward after connecting a node
  cur = cur.next;
  console.log(222,cur);
}

// Handle lists of unequal lengthscur.next = l1 ! = =null ? l1 : l2;
console.log(333,cur);
// return to the start node
console.log(444, head, head.next); // The val of head is undefined, so there is one more header than head.next
return head.next;
};
mergeTwoLists(l1, l2)
Copy the code

You can verify the code by yourself, repair speech big guy’s small book has carried out a lot of verification of this code, if there is a problem, welcome to communicate!

Delete linked list node

Delete a node from a linked list. Delete a node from a linked list. Delete a node from a linked list. Given a sorted linked list, delete all nodes that contain duplicate numbers, leaving only those numbers that are not duplicated in the original linked list. Example 1: input: 1 – > 2 – > 3 – > 3 – > 4 – > 4 – > 5 output: 1 – > 2 – > 5 example 2: input: 1-1-1 – > > > 2 – > 3 output: 2 – > 3

If this value is repeated, we will have to delete all the nodes of this value. Note that this is a sorted list. If this value is repeated, we will delete all nodes of this value. ————dummy node (😭)

Dummy = new ListNode() dummy. Next = headCopy the code

, similar to what is a virtual node, is used to our agents to use, actually does not exist, after all, if repeat the first nodes are removed, you take what directly select the third node, play a supporting role, let’s take a look at the code implementation process, use case is the result of a merge on list:

function deleteMultiple(l) {
    // If there are only 0 nodes, or one node will not repeat
    if(! l || ! l.next) {return
    }
    // new a dummy node that always points to our list
    const dummy = new ListNode()
    dummy.next = l
    // specify a pointer
    let cur = dummy

    // For a linked list loop, only if there are two subsequent nodes
    while(cur.next && cur.next.next) {
      // Determine the value of two nodes
      if(cur.next.val === cur.next.next.val) {
        // Record the equal value
        const equalVal = cur.next.val
        // Then delete each subsequent node as long as it equals this value
        while(cur.next && cur.next.val === equalVal) {
          cur.next = cur.next.next
        }
      }else{
        // If not, string it in
        cur = cur.next
      }
    }

    // The result of the loop is returned
    console.log(dummy.next);
    return dummy.next
}
deleteMultiple( l)
/ / {
// val: 1
// next: {
// val: 5
// next: {
// val: 6
// next: null
/ /}
/ /}
// }
Copy the code

Comments have been written in the code, should still be very clear, or repair speech big guy that sentence: “just read not write, go home to farm!” .

The progression of linked lists

Having learned the basics, let’s now look at some of the more useful and common pointer operations

How fast a pointer

How Pointers so luce, refers to have fast and slow two Pointers, when in the title of binary solution, we can only through time and time again traversal for what we want, but with how fast a pointer, we have a lot less effort on traversal, two Pointers a walk fast walk slowly, in repeated traversal in the title is very nice, Sometimes we will even use three Pointers, therefore, fast and slow Pointers + multi-pointer learning, for us to solve the traversal problem is very good, let’s look at a real problem!

Given a linked list, delete the NTH node from the penultimate 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 linked list becomes 1->2->3->5. Note: the given n is guaranteed to be valid.

In fact, this topic in the normal operation, we have no clue, because the linked list is to start from the beginning to find the target element, the normal idea is to first traverse, calculate the total length, iterate over the target location, and then delete, is not very troublesome, let’s take a look at the fast and slow pointer: The fast pointer goes n steps first, and then the fast and slow Pointers go at the same time. When the fast pointer goes to the end, the slow pointer happens to be in the first node before the target node, so it can be easily deleted. Let’s look at the code implementation 👇 :

// Replace linked lists with objects
let l = {
    val: 1 ,
    next: {
      val: 2 ,
      next: {
        val: 3 ,
        next: {
          val: 4 ,
          next: {
            val: 5 ,
            next: null
          }
        }
      }
    }
}
function deleteTarget(l, n) {
// create a dummy node, again using the class and dummy node above
const dummy = new ListNode()
Dummy next points to l
dummy.next = l
// Define two fast and slow Pointers, both to dummy
let fast = dummy, slow = dummy
// Let the fast pointer take n steps first
while(n) {
  fast = fast.next
  n--
}
// So when fast goes to the last node, the slow pointer points to the previous node to delete the node
while(fast.next) {
  slow = slow.next
  fast = fast.next
}
// Then make the slow node delete the next node
slow.next = slow.next.next
// Return the deleted l
console.log(dummy.next);
return dummy.next
}
deleteTarget(l,2)
/ / {
// val: 1 ,
// next: {
// val: 2 ,
// next: {
// val: 3 ,
// next: {
// val: 5 ,
// next: null
/ /}
/ /}
/ /}
// }
Copy the code

Multi-pointer applications

How Pointers, and we will read his brother a pointer, we also mentioned above, they are in order to solve the problem of traversing, in space, in time, so much, how useful is a pointer, we consider a bo: er, description: define a function, input a list of header node, to reverse the linked list and output inversion after the head of the linked list node. Example: input: 1 – > 2 – > 3 – > 4 – > 5 – > NULL output: 5 – > 4 – > 3 – > 1 – > 2 – > NULL

So what they’re saying here is let’s reverse, how do we reverse, we don’t have a reverse method for arrays, how do we do that? The linked list we learned before and after is actually made by the point of the next pointer. Does this mean that we can just drop the pointer a bit? Yes, it is such a way of thinking, so how to do it, we can take a look at the picture I draw, you can clarify the way of thinking 👇 :

As I said in the picture, it was really nice that we did this with multiple Pointers (I was on the wrong set @! @), which means that we use three Pointers pre, cur, and next to represent the context of the current node. We only need to change the next pointer to complete the inversion of the list.

// Use the example above
function reverseListNode(l) {
    // Let's define three Pointers, starting from the head node
    let pre = null.// The first node is empty
        cur = l // cur points to the header
    // Iterate through the list until there is no next node
    while(cur ! = =null) {
      // First record a node
      let next = cur.next
      // Change the pointer pointer
      cur.next = pre
      // Pre further
      pre = cur
      // cur forward
      cur = next
    }
    // After traversal, the pre node we return is the header
    console.log(pre);
    return pre
}
reverseListNode(l)
/ / {
// val: 5 ,
// next: {
// val: 4 ,
// next: {
// val: 3 ,
// next: {
// val: 2 ,
// next: {
// val: 1 ,
// next: null
/ /}
/ /}
/ /}
// }
Copy the code

This topic is indeed not difficult, and the idea will feel, oh, so ~, but, I think it is still to handwritten, see if you can achieve, because the logical order inside you can not make a mistake, if you feel that you can not understand, you draw a map, with a map is very good judgment.

After completing the complete list inversion, we will see his upgraded version, how to do local inversion, directly on the real topic 👇 : real topic description: inversion of the list from position M to n. Use a scan to complete the inversion. Description: 1 ≤ M ≤ N ≤ The length of the linked list. Example: input: 1 – > 2 – > 3 – > 4 – > 5 – > NULL, m = 2, n = 4 output: 1 – > > 4-3 – > 2 – > 5 – > NULL

Our idea is still the same, that is, we still want to consider the same as before, change the point of the node, but we look at this problem, in fact, is mainly to find the front node of m and the rear node of N, so we can reverse the node between M and N, take a look at the code to achieve 👇 :

function reversePart(l, m, n) {
    // First we need to define the front and current nodes, and define an auxiliary node to record the start node
    let pre, cur, handle
    // Initialize a dummy
    let dummy = new ListNode()
    dummy.next = l
    // define a p for traversal
    let p = dummy
    // loop to find the leading node
    for(let i = 0; i < m-1; i++) {
      p = p.next
    }
    // The p at the end of the loop is the leading node of the start node
    handle = p
    // record the start node
    let start = p.next
    // Go through the inversion
    pre = start
    cur = pre.next
    // Then we iterate between m and n again, reversing them
    for(let i = m; i < n; i++) {
      let next = cur.next
      cur.next = pre
      pre = cur
      cur = next
    }
    // After traversal, point m's leading node to pre after traversal
    handle.next = pre
    // cur points to the end of n
    start.next = cur
    // All complete, return
    console.log(dummy.next);
    return dummy.next
}
reversePart(l, 2.4)
/ / {
// val: 1 ,
// next: {
// val: 4 ,
// next: {
// val: 3 ,
// next: {
// val: 2 ,
// next: {
// val: 5 ,
// next: null
/ /}
/ /}
/ /}
// }
Copy the code

A circular linked list of postures

For circular lists, we should first solve the following problem:

How do I know if a linked list is looped

We start with a real problem: real problem description: given a linked list, determine whether there are rings in the list. Example 1: input: [3,2,0,4] output: true explanation: there is a ring in the linked list. Here is a picture in the problem.

In their thinking, it is like we are currently one of the nodes, if traversing the whole list, we can return to our own node, then must ring formation, for the place of the node, we can use a flag to indicate, as long as we can find the flag on the other nodes, so it must be the cyclization, Let’s look at the code implementation 👇 :

function hasCycle(l) {
     // Continue traversal as long as the node exists
    while(l){
        // If the flag is already set, the ring exists
        if(l.flag){
            return true;
        }else{
            // If no flag is set, set another flagDown l.f lag =true; l = l.next; }}return false;
}
Copy the code

Also one problem to derivatives as the above problem, also is to pinpoint a list into the ring of the first node, if there is a return to the node, if there are no returns null, this problem starting for we’ve learned how to judge whether the ring of thinking, is a simple, because we have found the first node, with flag is into the ring node, Specific everybody goes thinking by himself!

Another way of thinking about loop formation

Starting before we use the knowledge that can determine whether cyclization, yes, that is how a pointer, how to judge, slow pointer each time step, quick pointer take two steps at a time, if the ring so fast pointer will eventually one day meet, similar to running in the playground, we run faster when will meet again in a lap run slow students, we commonly known as the “ring”, Since we are running from a loop to a run, the same idea can be applied to a circular list. Let’s implement it in code:

function detectCycle(l) {
    // define a dummy node
    let dummy = new ListNode()
    dummy.next = l
    // define a p for traversal
    let p = dummy.next
    // Define a counter and a map space partition object
    let count = 0, map = {}
    / / traverse
    while( p && p.next ) {
      // Store each node in the map
      if(! map[p]) { map[p] = count }else {
      // If a saved count appears in the map, the proof has been returned
        return true
      }
      p = p.next
      count++
    }
    // If you can break out of the loop, it is not a loop
    return false
}
Copy the code

There are all kinds of ideas in the comments section of the booklet. I just post my ideas. Whether they are correct or lack of consideration needs to be verified completely

conclusion

Here, we list the advanced study ended, learned a lot this time, the list is mainly thought, so our key is to master his way, because wrote so many, we found that in fact every code be around next, so I hope you have a good digestion, must have to write about just know and understand!