As we all know in Dachang algorithm is must master, the following is my recent brush linked list of some summary, some of the solution to share with you

Reverse a linked list

Reverse a single linked list:

Example:

Input: 1 – > 2 – > 3 – > 4 – > 5 – > NULL

Output: 5 – > 4 – > 2 – > 3 – > 1 – > NULL

Answer key:

Reverse linked list is a basic problem in linked lists. My idea is as follows:

  • Define two Pointers: pre and cur; Pre before cur after.
  • Make the Pre’s Next point to cur each time, doing a local inversion
  • After a partial reversal, pre and CUR move forward one position at the same time

Code:

var reverseList = function(head) {    
    var prev = null    
    var curr = head    
    while(curr) {        
        var next = curr.next        
        curr.next = prev        
        prev = curr        
        curr = next    
    }    
    return prev
};
Copy the code

Cross linked list

Solution 1 (violence method) :

Iterate through list A, find the same value in list B as in list A, and return

if(! headA || ! headB) { return null } var AHead = headA while(AHead) { var BHead = headB while(BHead) { if(AHead == BHead) { return AHead } BHead = BHead.next } AHead = AHead.nextCopy the code

Solution 2 (two-pointer method) :

if(! headA || ! headB) { return null } var A = headAvar B = headB while(A ! == B) { A = A === null ? headB : A.next B = B === null ? headA : B.next } return ACopy the code

The middle nodule of a linked list

Answer key:

Finding the midpoint of the linked list can be used to find the double-pointer method, so that the fast pointer goes one step ahead of the slow pointer, when the fast pointer goes to the end, the slow pointer reaches the midpoint

Code:

var slow = headvar fast = head
while(fast && fast.next) {     
    slow = slow.next     
    fast = fast.next.next
}
return slow
Copy the code

Circular linked list

Answer key:

Double Pointers can be used for the detection of the circular linked list. Imagine that on the 400-meter track, when the fast runner catches up with the slow runner, it means there is an intersection between them. Let the fast pointer go first, and when the fast pointer catches up with the slow pointer, it means there is a ring

if(head == null || head.next == null) { return false } var slow = head var fast = head while(fast ! ==null && fast.next ! == null) { slow = slow.next fast = fast.next.next if(slow == fast) { return true } } return falseCopy the code

Palindrome list

Answer key:

First of all, we need to find the midpoint of the linked list, and then divide it into left and right parts with the midpoint. Let the right part carry out a reverse of the linked list, and compare each node of the left part of the linked list with the right one by one. If they are all the same, it is proved to be a palindrome linked list

Code:

Var isPalindrome = function(head) { Var right = reserve(findCenter(head)) var left = head == null) { if(right.val ! Next left = left. Next} return true} function findCenter(head){ var slow = head var fast = head while(fast && fast.next) { slow = slow.next fast = fast.next.next } return slow } // Function reserve(head) {var prev = null var curr = head while(curr) {var next = curr.next = prev prev =  curr curr = next } return prev }Copy the code

Deletes the penultimate node of the linked list

Code:

var removeNthFromEnd = function(head, n) { var preHead = new ListNode(0) preHead.next = head var slow = preHead, While (n--) {fast = fast. Next} // fast and slow go together while(fast && fast. Next) {fast = fast fast.next slow = slow.next } slow.next = slow.next.next return preHead.next };Copy the code