Algorithm series – linked list

You must know the following three points:

1. The traversal

2. Delete the

3. Insert the

How to solve the problem

Fast and slow pointer method

Double pointer method

Recursive method

Set method

Virtual pointer method

A reversal of the trend

1. Reverse linked lists

2. Locally reversed linked lists

3. Flip linked lists in groups of K

Solution:

Emphasis:

The entire list of inversion of the source back best,

 var cur = head;    
 var pre = null;   
 while(cur){        
  var temp = cur.next;       
   cur.next= pre;        
  pre = cur;        
  cur = temp;   
 }    
return pre;
Copy the code

The next 2 or 3 is nothing more than a list deletion and concatenation.

The template for the deletion process is as follows, for example, a local deletion:

 var newNode = new ListNode();   
newNode.next = head;   
var preLeftNode = newNode;   
i=1;  
while(preLeftNode&&i<left){       
 preLeftNode = preLeftNode.next;      
 i++;   
}   
var rightNode = preLeftNode.next   
var k=1;   
while(rightNode&&(k<right-left+1)){       
  rightNode = rightNode.next;       
  k++;   
}  
 var leftNode = preLeftNode.next;   
var temp =rightNode.next;   
preLeftNode.next = null;   
rightNode.next = null;   
preLeftNode.next = reverse(leftNode)    
leftNode.next =  temp   
return newNode.next;
Copy the code

Delete the nodes in the left-right range. Since there are deleted boundary nodes, we need to create virtual nodes to solve the problem.

Secondly, the former node and the node after the right node should be saved during the deletion process. The substitution is made by threading a needle.

And then k is always going to be I =1, and when I =0 you’re dealing with the length of the list.

Test point 2: ring series

1. Circular lists

2. The starting position of the circular list

Solution: standard fast and slow pointer method &hashMap method

Set method

 var setMap = new Set();    
var temp = head;
   while(temp){        
     if(setMap.has(temp)){  
          return temp;   
     }       
 setMap.add(temp);       
 temp = temp.next;   
 }    
return null;
Copy the code

Fast and slow pointer method

if(head==null||head.next==null){ return null; } var slow = head; var fast = head; while(fast&&fast.next){ fast = fast.next.next; slow = slow.next; if(fast==slow){ break; } } if(fast! =slow){ return null; } fast = head; while(slow! =fast){ fast = fast.next; slow = slow.next; } return slow;Copy the code

Sort lists and merge lists

1. Sort lists

2. Merge ordered linked lists

3. Insert sort the linked list

3. Merge two linked lists

4. Merge K ascending lists

Merge two linked lists

Solution: virtual pointer method

var mergeInBetween = function(list1, a, b, list2) {    
var newHead= new ListNode();   
 newHead.next = list1;    
var temp = newHead;    
var i=0;   
 while(temp.next&&i<a){    
    temp = temp.next;        
  i++;    
}    
var k=0;   
var obj = temp;   
 while(obj&&k<(b-a+1)){       
 obj = obj.next;        
k++;    
}
var left = temp;    
var right = obj.next;    
temp.next = null;    
obj.next = null;   
 var aa = list2;    
while(aa.next){        
 aa = aa.next;    
}    
left.next = list2;    
if(aa){         
 aa.next = right;   
 }      
 return newHead.next
};
Copy the code

Merge K ascending linked lists

var mergeKLists = function(lists) { if(! lists.length){ return null; } var i=1; var temp = lists[0]; while(i<lists.length){ temp = mergLinkTwo(temp,lists[i]) i++; } return temp; }; var mergLinkTwo = function(left,right){ var dumpy = new ListNode(); var p = dumpy; while(left&&right){ if(left.val<=right.val){ p.next = left; left = left.next; } else { p.next = right; right = right.next; } p = p.next; } if(left){ p.next = left; } if(right){ p.next = right; } return dumpy.next; }Copy the code

Test point 4: linked list intersection series

1. Linked list intersecting series

Solution: double pointer method

var lenA = getLength(headA); var lenB = getLength(headB); while(lenA! =lenB){ if(lenA>lenB){ headA = headA.next; lenA-- } else { headB = headB.next; lenB-- } } while(headA){ if(headA==headB){ return headB; } headB = headB.next; headA = headA.next; } return null }; var getLength = function(head){ var i=0; while(head){ head = head.next; i++; } return i;Copy the code

Delete elements

1. Remove duplicate nodes

2. Delete only one duplicate element from the sorted list

3. Delete all duplicate elements in the sorted list

4. Delete nodes in the linked list

5. Delete the NTH node from the list

Split linked lists

1. Split linked lists

2. Separate linked lists

Core idea: double pointer solution

var partition = function(head, x) {
    var temp = head;    
var minNode = new ListNode(0);    
var maxNode = new ListNode(0);    
var minHead = minNode;    
var maxHead = maxNode;    
while(temp){        
if(temp.val >= x){          
maxNode.next = temp;         
maxNode = maxNode.next;       
 } else {           
minNode.next = temp;           
minNode = minNode.next;        
}        
temp = temp.next;    
}    
maxNode.next = null;    
minNode.next = maxHead.next;      
 return minHead.next
};
Copy the code

Separated lists: The core is the process of connecting and reconnecting

var splitListToParts = function(root, k) { var length = getLen(root); var list =[]; if(k>length){ for (i=0; i<k; i++){ if(root){ list[i] = root; var temp = root.next; root.next = null; root = temp; } else { list[i] = null; } } } else { var count = Math.floor(length/k) var reminder = length%k; for(var i=0; i<k; i++){ list[i] = root; for(var j=0; j<count+(reminder>0? 1-0); j++){ root = root.next; } var temp = root.next; root.next = null; root = temp; } } return list; }; var getLen = function(head){ var i=0; var temp = head; while(temp){ temp = temp.next i++ } return i; }Copy the code

A palindrome linked list

1. Check whether the linked list is a palindrome linked list

The core idea of the solution: fast and slow pointer.

var isPalindrome = function(head) { var fast = head; var slow = head; while(fast&&slow&&fast.next){ fast = fast.next.next; slow = slow.next; } if(fast){ slow = slow.next; } var slow = trase(slow); var pre = head; while(slow){ if(pre.val! =slow.val){ return false } pre = pre.next; slow = slow.next; } return true; }; var trase = function(head){ var cur = head; var pre= null; while(cur){ var temp = cur.next; cur.next= pre; pre = cur; cur = temp; } return pre; }Copy the code

Switch any linked list node

1. Switch nodes in the linked list

2. Switch nodes in the linked list in pairs

Solution core: recursion

var swapPairs = function(head) {    
if(head==null||head.next==null){        
return head;    
}   
 var newHead = head.next;    
head.next = swapPairs(head.next.next);    
newHead.next = head;    
return newHead;
};
Copy the code

Add two numbers together

1. Add two numbers