Captain emoticons town building

# introduction

I heard there’s a class for free sex? You can’t miss it as a white whore. However, a class down, I people directly meng, this person is a robot?? It’s after 11:00. It’s past 11:00. The rest is on replay. Lecturer Hu Guang, people send nickname captain, Yang a good hand sail, open a good hand ship, ACM Asian gold medalist, self-proclaimed industry bottom line, Versailles master player, push-ups personally professor, keyboard terminator, its coding silky experience let me underground N layer players call: “code strong, horrible”! This series of articles attempt to record the learning process of this course, the topic is data structure and algorithm, brush questions mainly on Leetcode. I took you on the first voyage, sailing on their own – Captain Hu

The list

  • node
    • Data fields
    • Pointer to the domain
      • Implementation methods include address, subscript (relative address), reference
  • Chain structure
    • A linear structure is formed through the values of the pointer field
  • The characteristics of
    1. Each node in a linked list contains at least two parts: a data field and a pointer field
    2. Each node in the linked list forms a linear structure through the values of the pointer field
    3. Insert node O(1), delete node O(1)
    4. Not suitable for fast location data, suitable for dynamic insertion and deletion scenarios
  • Application scenarios
    • Dynamic memory allocation within the operating system
    • LRU (Least Recently Used) cache elimination algorithm

Captain’s words: to learn data structure, to learn algorithms, is to learn the way of thinking, not to learn the realization of specific programs, the realization of specific programs is based on programming experience, the same idea can be expressed in different ways

LeetCode liver questions (for training purposes)

    1. Circular linked list
// We can use the fast pointer to check whether the list has a ring. We can make the fast pointer move one step more than the slow pointer
var hasCycle = function(head) {
    if(! head)return false
    let p = head, q = head
    while(q && q.next) {
        p = p.next
        q = q.next.next
        if (p == q) return true
    }
    return false
};
Copy the code
    1. Circular linked list II
// First check if the list has a loop. When the list has a loop, let the q pointer (i.e. fast pointer) start from head. When the two Pointers meet, it is the first node to enter the loop
var detectCycle = function(head) {
    if(! head)return null
    let p = head, q = head.next
    while(q && q.next) {
        p = p.next
        q = q.next
        if (p == q) {
            q = head
            while(p ! = q) { p = p.next q = q.next }return p
        }
        q = q.next
    }
    return null
};
Copy the code
    1. Number of happiness
// If it is not a happy number, then the numbers must be ringed. Design a next function to return the next number
// If p and q are equal, the number is infinite. If Q goes to 1, it is happy
var nextNum = function(num) {
    let sum = 0
    while(num > 0) {
        sum += (num % 10) * (num % 10)
        num = parseInt(num / 10)}return sum
}
var isHappy = function(n) {
    if (n == 1) return true
    let p = nextNum(n), q = nextNum(nextNum(n))
    while(q ! =1&& nextNum(q) ! =1) {
        p = nextNum(p)
        q = nextNum(q)
        if (p == q) return false
        q = nextNum(q)
    }
    return true
};
Copy the code
    1. Reverse a linked list
// Three Pointers
var reverseList = function(head) {
    if(! head)return head
    let pre = null, cut = head, p = head.next
    while(cut) {
        cut.next = pre
        pre = cut
        cut = p
        if (p) p = p.next
    }
    return pre
};
// Recursive
var reverseList = function(head) {
    if(! head || ! head.next)return head
    let tail = head.next, p = reverseList(head.next)
    head.next = tail.next
    tail.next = head
    return p
};
Copy the code
    1. Reverse linked list II
// Modify the implementation of reverse linked list to reverse n nodes
var reverseN = function(head, n) {
    if (n == 1) return head
    let tail = head.next, p = reverseN(head.next, n - 1)
    head.next = tail.next
    tail.next = head
    return p
}
// Define a virtual head that points to head, and a p pointer that points to the previous node of the reverse node according to the value of left
// make p's next point to the inverted list
var reverseBetween = function(head, left, right) {
    let ret = new ListNode(null, head), p = ret, num = right - left + 1
    while(--left) {
        p = p.next
    }
    p.next = reverseN(p.next, num)
    return ret.next
};
Copy the code
    1. Flip linked lists in groups of K
// Reverse list n node method
var __reverseN = function(head, n) {
    if (n == 1) return head
    let tail = head.next, p = __reverseN(head.next, n - 1)
    head.next = tail.next
    tail.next = head
    return p
}
If the number of nodes left is less than n, return head directly
var reverseN = function(head, n) {
    let cut = n, p = head
    while(--n && p) p = p.next
    if(! p)return head
    return __reverseN(head, cut)
}
// Define a virtual header ret to head, p to ret (p to the previous node of the inversion node), and q to p.next (also the previous node of the next node to be reversed after the inversion).
// set p.ext to point to the inverted node. If it is equal to q, the inversion is complete and ret.next is returned
// If p = q, p = q, p = q, q = q.ext, p = q, q = q.ext, p = q, q = q.ext
var reverseKGroup = function(head, k) {
    let ret = new ListNode(null, head), p = ret, q = p.next
    while((p.next = reverseN(q, k)) ! = q) { p = q q = q.next }return ret.next
};
Copy the code
    1. Rotating list
// Define p to point to the end node and calculate the length of the linked list
// Rotate right k times is the same length as rotate left -k times (rotate left easier, point head to next)
// Disconnect the end node from the head node
var rotateRight = function(head, k) {
    if(! head)return head
    let p = head, cut = 1
    while(p.next) {
        p = p.next
        cut++
    }
    console.log(cut)
    p.next = head
    k = cut - k % cut
    while(k--) {
        head = head.next
        p = p.next
    }
    p.next = null
    return head
};
Copy the code
    1. Pairs swap nodes in a linked list
// Invert a list of 25
var swapPairs = function(head) {
    let ret = new ListNode(null, head), p = ret, q = p.next
    while((p.next = reverseN(q, 2)) != q) {
        p = q
        q = q.next
    }
    return ret.next
};
Copy the code
    1. Delete the penultimate node of the linked list
// Define a virtual header that points to the header, a p pointer to the virtual header, and a q pointer to the header
// Move the pointer to q by n. If q is null, the NTH to last node is the head
// Otherwise, let p and q move together. When q points to null, p points to the previous node of the node to be deleted
var removeNthFromEnd = function(head, n) {
    if(! head)return head
    let ret = new ListNode(null, head), p = ret, q = p.next
    while(n--) {
        q = q.next
    }
    if(! q)return head.next
    while(q) {
        p = p.next
        q = q.next
    }
    p.next = p.next.next
    return ret.next
};
Copy the code
    1. Removes duplicate elements from sorted linked lists
// define pointer p to traverse the comparison value
var deleteDuplicates = function(head) {
    let p = head
    while(p && p.next) {
        if (p.val == p.next.val) {
            p.next = p.next.next
        } else {
            p = p.next
        }
    }
    return head
};
Copy the code
    1. Delete duplicate element II from sorted linked list
// define a pointer p to traverse the comparison value, and define a pointer q to continue the query when the same element is found
var deleteDuplicates = function(head) {
    let ret = new ListNode(null, head), p = ret, q
    while(p.next) {
        if (p.next.next && p.next.val == p.next.next.val) {
            q = p.next.next
            while(q && q.val == p.next.val) {
                q = q.next
            }
            p.next = q
        } else {
            p = p.next
        }
    }
    return ret.next
};
Copy the code
    1. Separated list
Ret1 = ret2; ret1 = ret2; ret1 = ret2
var partition = function(head, x) {
    let ret1 = new ListNode(0.null), ret2 = new ListNode(0.null), p1 = ret1, p2 = ret2, q = head
    while(q) {
        if (q.val < x) {
            p1.next = q
            p1 = p1.next
            q = q.next
        } else {
            p2.next = q
            p2 = p2.next
            q = q.next
        }
    }
    p2.next = null
    p1.next = ret2.next
    return ret1.next
};
Copy the code
    1. Copy a linked list with a random pointer
var copyRandomList = function(head) {
    if(! head)return head
    let p = head, new_head, q;
    // Copy the current node and insert after the current node to get a copied linked list
    while(p) {
        q = new Node(p.val)
        q.next = p.next
        q.random = p.random
        p.next = q
        p = q.next
    }
    // Iterate through the list and modify the pointer to the random pointer
    p = head.next
    while(p) {
        if (p.random) p.random =  p.random.next
        p = p.next
        if (p) p = p.next
    }
    // Join the replicated nodes together to form a new linked list
    p = head
    new_head = head.next
    while(p) {
        q = p.next
        p.next = q.next
        if (p.next) q.next = p.next.next
        p = p.next
    }
    return new_head
};
Copy the code