[JS] - [linked list - application] - learning notes

Statement ： This note is based on the Nuggets brochure , If you want to learn more details , Please move https://juejin.cn/book/6844733800300150797

1 The combination of linked lists

describe ：
Merge two ordered lists into a new ordered list and return . The new linked list is composed of all nodes of a given two linked lists
Input ：
1->2->4,
1->3->4
Output ：
1->1->2->3->4->4

Ideas :
The red arrow in the figure below indicates the process and direction of needle threading

1. Create a new header node , Create a pointer cur, As a needle
2. String the smaller node , The pointer moves forward , At present cur The pointer also moves forward
3. Finally, handle the unfinished linked list , Spell last
   

const mergeTwoLists = function(l1, l2) {
    
  #1  Define header node , Make sure the linked list can be accessed 
  let head = new ListNode()
  // cur  This is our one “ The needle ”
  let cur = head
  // “ The needle ” Start in  l1  and  l2  Shuttling between 
  while(l1 && l2) {
    
      # 2.1 If  l1  The node value of is small , String up first  l1  The node of ,l1 Walk forward 
      if(l1.val<=l2.val) {
     
          cur.next = l1
          l1 = l1.next
      } else {
    
       #2.2  If l2  More hours , String up  l2  node ,l2  Step forward 
          cur.next = l2
          l2 = l2.next
      }
     #3 “ The needle ” After concatenating a node , Will also take a step forward 
      cur = cur.next 
  }
  #4  Deal with the unequal length of the linked list 
  cur.next = l1!==null?l1:l2
  //  Return to the starting node 
  return head.next
};

2 Deletion of linked list nodes

1. Delete all duplicate elements

describe ：
Given a sorted linked list , Delete all duplicate elements , So that each element only appears once .

Input :
1->1->2
Output : 1->2

Input : 1->1->2->3->3
Output : 1->2->3

const deleteDuplicates = function(head) {
    
    #1  Set up  cur  The pointer , The initial position is the first node of the linked list 
    let cur = head;
    #2  Traversing the linked list 
    while(cur != null && cur.next != null) {
    
        if(cur.val === cur.next.val) {
    
         # 2.1  If the value of the current node is equal to that of the following node （ repeat ）, Delete the next node （ duplicate removal ）
            cur.next = cur.next.next;
        } else {
    
         # 2.2  If not repeated , Continue traversing 
            cur = cur.next;
        }
    }
    return head;
};

2 Delete all nodes with duplicate numbers

describe ：
Given a sorted linked list , Delete all nodes with duplicate numbers , Keep only the original list No recurring numbers

Input :
1->2->3->3->4->4->5
Output :
1->2->5

Input :
1->1->1->2->3
Output :
2->3

Ideas :
The first node of the linked list , Because there is no precursor node , We have no way to deal with it . Then we can use a dummy Nodes to solve this problem .
1 Definition dummy node , Point to the head node ,cur from dummy Traverse
2. Meet the same , Record val Value , Start loop traversal , Delete the same . If not, skip
3 return dummy.next, That is, the starting node of the linked list

const deleteDuplicates = function(head) {
    
    #1  In extreme cases ：0 Or 1 Nodes , Will not repeat , Go straight back to 
    if(!head || !head.next) {
    
        return head
    }
    #2 dummy  On stage ,dummy  Always point to the head node 
    let dummy = new ListNode()  
    dummy.next = head   
    
    #3 cur  from  dummy  To traverse the 
    let cur = dummy 
    //  When  cur  When there are at least two nodes behind 
    while(cur.next && cur.next.next) {
    
        //  Yes  cur  The latter two nodes are compared 
        if(cur.next.val === cur.next.next.val) {
    
            //  If the value is repeated , Then write down this value 
            let val = cur.next.val
            //  Repeatedly check whether the following elements repeat the value multiple times 
            while(cur.next && cur.next.val===val) {
    
                //  If you have any , Delete 
                cur.next = cur.next.next 
            }
        } else {
    
            //  If not repeated , Normal traversal 
            cur = cur.next
        }
    }
    //  Return the starting node of the linked list 
    return dummy.next;
};

dummy node , Template code

const dummy = new ListNode()
//  there  head  Is the original first node of the linked list 
dummy.next = head

3 Delete the last of the linked list N Nodes （ Speed pointer ）

describe ：
Given a linked list , Delete the last of the linked list n Nodes , And return the head node of the list .

Given a linked list : 1->2->3->4->5, and n = 2.
When the penultimate node is deleted , Linked list becomes 1->2->3->5.

Ideas :

1. Definition dummy The node is the precursor of the head node , Both the speed and the speed of the pointer dummy Start
2. Let's go first n Step ,
3. The fast and slow pointers start to move synchronously ,
4. Delete the successor of slow pointer , Countdown n Nodes
5. return dummy.next, Head node
   

const removeNthFromEnd = function(head, n) {
    
    #1  initialization  dummy  node , Point to the head node 
    const dummy = new ListNode()
    dummy.next = head
    
    #2  Initialize speed pointer , All pointing dummy
    let fast = dummy
    let slow = dummy

    #3  Hurry up and walk slowly  n  Step 
    while(n!==0){
    
        fast = fast.next
        n--
    }
    
    #4  Go with the hands 
    while(fast.next){
    
        fast = fast.next
        slow = slow.next
    }
    
    #5  The slow pointer deletes its own successor node 
    slow.next = slow.next.next
    //  Return to header node 
    return dummy.next
};

4.0 Reverse of linked list （ Multi pointer ）

describe ：
Define a function , Enter the head node of a linked list , Invert the linked list and output the head node of the inverted linked list

Input : 1->2->3->4->5->NULL
Output : 5->4->3->2->1->NULL

Ideas ：

1. Precursor node pre, The current node cur, Successor node next
2. next Point to pre, then pre and cur Continue to move back
3. Finally back to pre , Is the head node of the new linked list
   

const reverseList = function(head) {
    
    #1  The initialization precursor node is  null
    let pre = null;
    #2  Initialize the target node as the header node 
    let cur = head;
    
    #3  As long as the target node is not  null, Traversal must continue 
    while (cur !== null) {
    
        //  Make a note of  next  node 
        let next = cur.next;
        //  Reverse pointer 
        cur.next = pre;
        // pre  Take a step forward 
        pre = cur;
        // cur Take a step forward 
        cur = next;
    }
    //  After the reversal ,pre  It will become the head node of the new linked list 
    return pre
};

4.1 Locally invert a linked list

describe ：
Reverse from position m To n The linked list of . Please use a scan to complete the inversion .

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

Ideas

1. First define dummy, find m The precursor of , And save it lefthead
2. from m As pre,cur Point to pre.next Start flipping
3. hold leftHead Point to pre,start Point to cur
   

//  The input parameter is the header node 、m、n
const reverseBetween = function(head, m, n) {
    
    //  Definition pre、cur, use leftHead To undertake the precursor node of the whole section 
    let pre,cur,leftHead
    #1  dummy node 
    const dummy = new ListNode()  
    dummy.next = head
    
    #2.0 p It's a cursor , Used to traverse the , At first it pointed to  dummy, Go straight ahead  m-1  Step , Go to the precursor node of the whole section 
    let p = dummy  
    for(let i=0;i<m-1;i++){
    
        p = p.next
    }
    #2.1  Cache this precursor node to  leftHead  in 
    leftHead = p
    let start = leftHead.next   // start  Is the first node of the inversion interval 
    pre = start// pre  Point to start
    cur = pre.next // cur  Point to  start  Next node of 
    
    #3  Start repeating the reverse action 
    for(let i=m;i<n;i++){
    
        let next = cur.next//  Make a note of  next  node 
        cur.next = pre //  Reverse pointer 
        pre = cur// pre  Take a step forward 
        cur = next // cur Take a step forward 
    }
    #4  leftHead  The subsequent node of is now the first node of the inverted interval 
    leftHead.next = pre
    start.next=cur //  The last node after reversing the interval  next  Point to  cur
  
    return dummy.next  // dummy.next  Always point to the chain header node 
};

5 Judge whether the linked list is looped

1. Change the node ,flag

const detectCycle = function(head) {
    
    while(head){
    
        if(head.flag){
    
            return head;
        }else{
    
            head.flag = true;
            head = head.next;
        }
    }
    return null;
};

2. It can be used map simulation （ I like , Keep in mind ）

const detectCycle = function(head) {
    
	const visited = new Map();
    while(head){
    
        if(visited.has(head)){
    
            return head;
        }else{
    
            visited.set(head)
            head = head.next;
        }
    }
    return null;
};

3. Speed pointer

Let's go two steps , Slow pointer one step
If they are equal, there is a ring

const detectCycle = function(head) {
    
   if(!head) return null;
   let slow=head,fast=head;
	#1  Go ahead before the end of the pointer 
   while (fast !== null) {
    
   		#2  Slow pointer one step , Let's go two steps 
        slow = slow.next;
        if (fast.next !== null) {
    
            fast = fast.next.next; 
        } else {
    
            return null;
        }

		#3  If the fast and slow hands meet 
        if (fast === slow) {
    
            let ptr = head;
            while (ptr !== slow) {
    
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }
    return null;
};

Let's use an extra pointer ptr.
start , It points to the head of the linked list
; And then , It and slow Move back one position at a time . Final , They will meet at the entry point .