The list

Linked lists are used in the React update and are common in interviews. There are two basic linked forms: single linked list and ring linked list;

Pre –

Create a list

 class LinkNode {
    constructor(value){
      this.value = value;
      this.next = null; }}Copy the code

Create the entire linked list

function createLink(){
    this.head = null;
 }
 createLink.prototype.add=function(value){
   let linknode = new LinkNode(value)
   if(!this.head){
     this.head = linknode;
   }else{
     // Add the current list to the end of the list
     this.insertNode(linknode)
   }
 }
 createLink.prototype.insertNode=function(node){
   let curr = this.head;
   while(curr){ 
     if(! curr.next){ curr.next = node;return; } curr = curr.next; }}Copy the code

Singly linked lists

Gets the list length

function getLinkLength(link){
   if(! link)return 0
   let number = 1;
   let curr = link;
   while(curr){
     number++;
     curr = curr.next;
   }
   return  number;
 }
Copy the code

Outputs the penultimate KTH node of a singly linked list

Outputs the last node
Traversing the list from front to back, if + th k== the length of the list is the current node

Start from the beginning to the end

/** * returns the last KTH element *@param {*} link 
 * @param {*} k 
 */
function getKlineNode(link,k){
  // Get the current link length
  let linkSize = getLinkLength(link);
  if(linkSize <k) return null;
  let curr = link,nu =1;
  while(curr){
    if(k+nu == linkSize){
      return curr.value;
    }
    nu++;
    curr = curr.next;
  }
  return null;
}
Copy the code

Recursive method

Let’s define num = k
Iterate to the end of the list recursively.
Return num minus 1 each time starting at the end
When num is 0, the destination node can be found

let num = 0
function dgGetKlineNode(link,k){
  num = k;
  if(! link)return null;
  let curr = dgGetKlineNode(link.next,k)
  // Current value returns to continue traversal
  if(curr){
     return curr;
  }else{
    // If no value exists, the current traversal is complete
    num --;// subtract 0 recursively once
    if(num ==0) {// If num is 0, the node is reached
       return link.value
    }
  }
  return null
}
Copy the code

FIG. 1 Find the KTH node from last to last

Double pointer method

function dobuleGetKeyLink(link,key){
  if(! link)return null
  let curr = link,curr2 =link;
  // Curr2 takes k steps first
  for(var i =0; i<key; i++){ curr2 = curr2.next; }// The value of curr2 is in the penultimate KTH position
  while(curr2){
    curr2 = curr2.next;
    curr = curr.next;
  }
  return curr.value 
}

Copy the code

* Prints the linked list from end to end

Use three-party space to store the tree structure that has been traversed currently

non-recursive

function printReverseLink(link){
  // Use stack to store the traversal structure
  let stack = [];
  let curr = link;
  while(curr){
    stack.unshift(curr.value)
    curr=curr.next;
  }
  return stack.join("- >")}let result = printReverseLink(link.head)
console.log(result)
Copy the code

recursive


let stackdB = []
function dbPrintReverseLink(link){
  // The current node is not empty
    if(link){
      // Continue traversing the next element
      if(link.next! =null){
        dbPrintReverseLink(link.next)
      }
      // Then store the current node, ensuring that the following nodes are in front of the current node
      stackdB.push(link.value)
    }
}
dbPrintReverseLink(link.head);
console.log(stackdB.join("- >"))
Copy the code

* Reverse linked lists

The inversion of a linked list, i.e., the forward and backward transposition, has a nominal tail

List traversal
Define the pre node
Define a back node node to move the pointer backwards

function reverseLink(link){
  if(! link)return null; 
  let pre = null,pReversedHead;
  let curr = link; 
  while(curr){
    let needNext = curr.next;// Create a temporary next
    // Switch the current orientation of pre and curr
    curr.next = pre;
    pre = curr;  
    curr = needNext;   
  }    
  return pre 
}
Copy the code

* Delete nodes in linked list, required time complexity O (1)

If key == linknode. value exists, delete it
Note the deletion of the boundary value, which may be the last element

function deleteSingleNode(link,node){
  if(! link)return null;
  let curr = link,pre=null;
  while(curr){
     // If it exists, delete it
    if(curr.value == node){ 
      // Not deleted in the last one
      if(curr.next){
        curr.value = curr.next.value;
        curr.next =  curr.next.next;
        break;
      }else{
        // The last element
        pre.next = null;
        break;
      }  
    } 
    pre = curr;
    curr  = curr.next; 
  }
  // Clear the empty element
}
Copy the code

Delete duplicate nodes in the linked list

Whether to keep a node Given an ordered linked list, if there is more than one same node, the element value of the node is deleted.

Given that the conditions are ordered so that we don’t have to iterate;
If the list is unordered, there is no need to delete it;

Idea – : Iterate through the list, record the elements, if there are the same then delete all


 function deleteMoreNode(link){
    if(! link)return null
    let curr = link,pre = link;
    // The first one is special
    if(curr.next && curr.value == curr.next.value){
      var isFirst = true;
    }
    while(curr){
      // Compare the current one to the next one
      if(curr.next){
        // Two elements are equal
        if(curr.value == curr.next.value){
          // Continue traversing until unequal
          while(curr.next && curr.value == curr.next.value ){
            curr = curr.next;
          }  
          curr = curr.next;  
          pre.next = curr;   
        }else{ pre = curr; curr = curr.next; }}else{ curr=curr.next; }}// Delete the first element if the first element is equal
    if(isFirst){  
      if(link.next){
        link.value = link.next.value;
        link.next = link.next.next || null; 
      }else{ 
        link.value = null}}}Copy the code

Other ideas:

Traverse the linked list and keep it in the stack. Each time, compare whether the element needs to exist in the stack. If it does, delete it; if it does not, continue

function deleteMoreNodeStack(link){
  if(! link)return null;
  let stack =[];
  stack.push(link.value)
  let curr = link.next,pre = link; 
  while(curr){ 
    if(stack.indexOf(curr.value)>-1) {// The current element exists for deletion
      while(stack.indexOf(curr.value)>-1){  
         curr = curr.next;
         // The element does not exist
         if(! curr){ pre.value =null;
           pre.next = null
           return; }}if(curr){ stack.push(curr.value) pre.value = curr.value; pre.next = curr.next; }}else{ 
      stack.push(curr.value)
      pre = curr;   
    }
    curr &&  (curr = curr.next) 
  } 
   
}
Copy the code

* The first common node in two linked lists

Ideas:

The pointer to a singly linked list points to the next node. If the first common node of two singly linked lists means that the nodes following them are all together. Like the image below, due to the length of the two list may not be consistent, so the length of the first to compare the two list m, n, and then use two Pointers point to the two list head node, and make a long list of Pointers go | m – n | length, node is the same, if they have the following means the first public node.

const getLinkLength = require('./link-length')
 function findSameNode(link1,link2){
   if(! link1 || ! link2)return null;
   // Calculate the length of two lists
   let size1 = getLinkLength(link1);
   let size2 = getLinkLength(link2);
   let  n = size1- size2;
   let mH = null,sH = null;//mH stores long lists. SH stores short lists
   if(n>0){
      mH=link1;
      sH=link2
   }else{
     mH=link2;
     sH=link1
   }
   // The big one goes first
   n =Math.abs(n)
   while(n){
     mH = mH.next;
     n--;
   }  
   // Both mH and sH have the same length
   while( (mH && sH) && mH.value ! =sH.value){ mH= mH.next; sH = sH.next; }return mH;
 }
Copy the code

Use linked lists to add large numbers

Problem description Two integers represented by linked lists, where each node contains a number. The numbers are stored in the reverse order of the original integers, such that the first number is at the beginning of the list. Write a function that adds two integers and returns the sum as a linked list.

The input3->1->5->null
5->9->2->nullAnd the output8->0->8->null
Copy the code

When you add a list
Whether there is a carry
Whether there is an unfinished part after the final completion


 function comSumNode(link1,link2){
   if(! link1 || ! link2) {return link1 || link2
   }
   let curr1 =link1,curr2 = link2;
   // the sum used in the calculation will always indicate whether there is a carry or not
   let t = new createLink(),sum=0;
   while(curr1 && curr2){ 
     let value = curr2.value + curr1.value; 
     // Check whether the preceding digit has a carry
     value = sum ? value+1 : value;
     sum = 0 
     // Whether the current t.value is greater than 0 if it is, the next bit needs to be carried
     if(value>10){
       sum=1;
       value =value -10;
     }  
    t.add(value)
    curr2 = curr2.next;
    curr1 = curr1.next; 
   }
   // Check if sum,curr2, and curr1 have any remaining elements
   while(curr1){
     value = sum? curr1.value+sum:curr1.value;
     sum =0;
     if(value>=10){
       sum =1
       value = value-10
     }
     t.add(value)
     curr1= curr1.next;
   }
   while(curr2){
    value = sum? curr2.value+sum:curr2.value;
    sum =0;
    if(value>=10){
      sum =1
      value = value-10
    }
    t.add(value)
    curr2= curr2.next;
  }
  // There is also sum
  if(sum){
    t.add(sum)
  }
   return t.head;
 }
Copy the code

Ordered list merge

Title: Merge two ordered lists into a new ordered list and return. A new list is formed by concatenating all the nodes of a given two lists.

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

routine

A. Iterate over two linked lists and compare their sizes
B. Push small elements into the new list

 /** * Merge two ordered lists *@param {*} link1 
  * @param {*} link2 
  */
function mergeLink(link1,link2){
  if(! link1 && ! link2){return link2 || link1;
  }
  let newLink = new createLink();
  let curr1=link1,curr2=link2;
  while(curr1 && curr2){ 
    if(curr1.value > curr2.value){
      // If the element of link2 is small and pushes the element of 2 into the new list then the pointer of 2 moves backwards
      newLink.add(curr2.value);
      curr2 =curr2.next;
    }else{ newLink.add(curr1.value); curr1 =curr1.next; }}// Check to see if there are any remaining elements
  while(curr2){
    newLink.add(curr2.value);
    curr2 = curr2.next;
  }
  while(curr1){
    newLink.add(curr1.value);
    curr1 = curr1.next;
  }
  return newLink;
}

let result = mergeLink(link2.head,link.head)
result.print()
Copy the code

Recursive thought

If pHead1 is empty, return pHead2; if pHead2 is empty, return pHead1.
Compare the size of the first node of the two lists to determine the position of the head node
After the head node is determined, continue to select the next node from the remaining nodes to link to the node selected in the second step, and then continue to repeat steps (2) and (3) until the linked list is empty.

// Recursive implementation
function dgMergeLink(link1,link2){
  let newLink = new LinkNode();
  // if link1 or link2 is empty, return the other
  if(link1 ==null) {return link2;
  }else if(link2 ==null) {return link1
  }else{
     // Compare two sizes
     if(link2.value > link1.value){
       newLink = link1; // press link1 to continue traversing link1.next
       newLink.next = dgMergeLink(link1.next,link2)
     }else{
      newLink = link2; // press link2 to continue traversing link2.next
      newLink.next = dgMergeLink(link1,link2.next)
     }
     return newLink 
  } 
}
let result1 = dgMergeLink(link2.head,link.head) 
let r = new createLink();
r.header = result1;
r.print()
Copy the code

Circular linked list

A ring in a single linked list means that the next pointer of the node at the end of the list is not NULL, but points to a node in the list, resulting in a ring structure in the list.

FIG. 2 Structure of ring linked list

For the last node 8, instead of pointing to NULL, next points to 3, forming a ring structure.

Check if there are returns in the linked list

Label recording

Traversal the linked list, the visited mark is 1, if traversal to a node is exactly visited, then there is a ring, otherwise there is no;

/** * Check whether the list has a loop */
function isCommonRing(link){
  let curr = link;
  while(curr){
    // If it has been accessed, it has a ring
    if(curr.isVisted){
      return true;
    }
    curr.isVisted = 1; 
    curr =curr.next
  }
  return false;
}
Copy the code

Build the set table

How fast a pointer

Define two Pointers to slow and fast, and point to the head of the list.
The slow pointer advances one node at a time, and the fast pointer advances two nodes at a time.
When slow and fast are equal, and neither of them is empty, the linked list has a ring.

function isHaveRingFast(link){
  let slow = link;
  let fast = link;

  while(slow && fast.next){
    slow = slow.next;/ / pointer to slow
    fast = fast.next.next;/ / pointer
    if(slow.value == fast.value){
      return true; }}return false;
}
Copy the code

Find the entry node for the loop

The slow pointer moves forward one node at a time, so when slow meets fast, slow has not traversed the entire linked list. Set s for slow and 2s for fast. Set the distance from the entry point of the ring to the head node as A, the distance from the first encounter point of slow and fast to the entry point as B, and the length of the ring as R.

FIG. 3 Circular linked list diagram

If the ring length is r, the distance traveled by slow =a+b the distance traveled by Fast 2s =a+b +n *r (n represents the number of laps traveled) s= n *r; Means that the slow pointer travels an integer multiple of the length of the ring. If the degree between the head node of the list and the end node of the ring is L, the distance between the meeting node of slow and fast and the entry node of the ring is X. A +X = s = n * r = (n -1) * r + (L - a);
a = (n - 1) * r + (L - a - X); (it just points to the entry node, which requires derivation O) Starting from the encounter point of slow and fast, a pointer P1 moves forward (L-A-x), then the pointer reaches the entry node. At the same time, p2 starts at the beginning and advances a step. When P1 meets P2, both P1 and P2 point to the entry node. (L-A-x) is the distance from the encounter point to the entry pointCopy the code

function getMeetNode(link){
  let slow = link;
  let fast = link;
  while(slow && fast.next){
    slow = slow.next;/ / pointer to slow
    fast = fast.next.next;/ / pointer
    if(slow.value == fast.value){
      returnslow; }}return null;
}

// Find the entry node based on the entry node
function findEntry(link){
  let node = getMeetNode(link);
  if(! node)return null;
  let p1 = node;
  let p2 = link;
  while(p1 ! = p2){ p1=p1.next; p2=p2.next }return p2
}
Copy the code

Calculating loop length

Calculate according to the encounter points found; In Figure 3, the meeting node of Slow and FAST is found, so that solw and FAST Pointers start from the meeting node. According to the previous advance rules, when slow and FAST meet again, the length of slow traversing is exactly the length of the ring. Find the meeting point: Purposely draw flow charts

Figure 4. Calculation of circular linked list diagram


function comRingLength(link){
  if(! link)return null;
  let fast = link;
  let slow = link;
  // Find the encounter point
  while(fast.next && slow){
    fast =fast.next.next;
    slow = slow.next
    if(fast == slow){
      break; }}// Keep going
  slow =slow.next; 
  fast = fast.next.next;
  let num = 1;
  // When they meet again;
  while(slow ! = fast){ fast = fast.next.next; slow = slow.next; num ++; }return num; 
}
let number = comRingLength(link.head)
console.log(number)
Copy the code

Reference documentation

A 10,000-word linked list
Linked lists often meet questions

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.

Front-end basic algorithm summary – linked list

The list

Pre –

Create a list

Create the entire linked list

Singly linked lists

Gets the list length

Outputs the penultimate KTH node of a singly linked list

Recursive method

Double pointer method

* Prints the linked list from end to end

non-recursive

recursive

* Reverse linked lists

* Delete nodes in linked list, required time complexity O (1)

Delete duplicate nodes in the linked list

Idea – : Iterate through the list, record the elements, if there are the same then delete all

Other ideas:

* The first common node in two linked lists

Use linked lists to add large numbers

Ordered list merge

routine

Recursive thought

Circular linked list

Check if there are returns in the linked list

Label recording

Build the set table

Find the entry node for the loop

Calculating loop length

Reference documentation

Front-end basic algorithm summary – linked list

The list

Pre –

Create a list

Create the entire linked list

Singly linked lists

Gets the list length

Outputs the penultimate KTH node of a singly linked list

Recursive method

Double pointer method

* Prints the linked list from end to end

non-recursive

recursive

* Reverse linked lists

* Delete nodes in linked list, required time complexity O (1)

Delete duplicate nodes in the linked list

Idea – : Iterate through the list, record the elements, if there are the same then delete all

Other ideas:

* The first common node in two linked lists

Use linked lists to add large numbers

Ordered list merge

routine

Recursive thought

Circular linked list

Check if there are returns in the linked list

Label recording

Build the set table

Find the entry node for the loop

Calculating loop length

Reference documentation

Related Posts

Web pages implement the clock canvas

How can I exit the Node script safely when it encounters an exception

Regular expression an introduction