Algorithm Small Daily-02

Posted May 27, 20203 min read

[160]Intersect linked list

Another requirement is that the space complexity is O(1)
The first solution:both time and space complexity are O(n)
Add a label to headA loop, and then loop headB to determine whether headB has a marked node, if it is, it is an intersecting node, and if not, it returns NULL.

function getIntersectionNode

(headA, headB) {
while(headA) {
headA.flag = true
headA = headA.next
}
while(headB) {
if(headB.flag) return headB
headB = headB.next
}
return null
};

The second solution:This question is mainly to examine the usage of double pointers. If A and B intersect, then the linked list of A and B from the intersection node is consistent.
We can try to eliminate the difference between the lengths of the A and B linked lists, and start from the same number of positions to determine whether there are the same nodes. Otherwise it returns null and the two linked lists do not intersect.
Time complexity:O(n)

Space complexity:O(1)

var getIntersectionNode = function(headA, headB) {
    //Clear height difference
    let pA = headA, pB = headB
    while(pA || pB) {
        if(pA === pB) return pA
        pA = pA === null? headB:pA.next
        pB = pB === null? headA:pB.next
    }
    return null
};

[206]Reverse a singly linked list

Recursive and iterative methods are required
The first method iteration method:
Time complexity:O(n)
Space complexity:O(1)

function reverseList(head) {
    if(! head ||! head.next) return head
    var prev = null, curr = head
    while(curr) {
        //Used to temporarily store curr successor nodes
        var next = curr.next
        //Reverse the successor pointer of curr
        curr.next = prev
        //Change prev, curr
        //The node to be reversed points to the next node
        prev = curr
        curr = next
    }
    head = prev
    return head
};

The second method:recursive method
Time complexity:O(n)
Space complexity:O(n)

function reverseList(head) {
    if(! head ||! head.next) return head
    var next = head.next
    //recursively reverse
    var reverseHead = reverseList(next)
    //change pointer
    next.next = head
    head.next = null
    return reverseHead
};

\ [217 ]Given an integer array, determine whether there are duplicate elements

The main subject of this question should be Set
method one:
At the beginning, I thought of one of the most stupid methods, the brute force method, and the two layers of loops are compared one by one. The super has no technical content. In fact, it can be sorted first, but it is not the simplest solution.

/**
* @param {number []} nums
* @return {boolean}
* /
var containsDuplicate = function(nums) {
for(var i = 0; i <nums.length; i ++) {
for(var j = 0; j <nums.length; j ++) {
if(nums [i]== nums [j]&& i! = j) {
return true;
}
}
}
return false;
};

Method two:refer to the solution and get it with one line of code
set deduplication and compare size

var containsDuplicate = function(nums) {
    return!(nums.length === new Set(nums) .size);
};

[235]The nearest common ancestor of a binary search tree:given a binary search tree, find the nearest common ancestor of two specified nodes in the tree

Then the first question point is the definition of the most recent public ancestor:The definition of the most recent public ancestor in Baidu Encyclopedia is:"For the two nodes p and q of the rooted tree T, the most recent public ancestor is represented as a node x, x is the ancestor of p and q and the depth of x is as large as possible(a node can also be its own ancestor). "
Problem Solution:Use the characteristics of a binary search tree. The law of size can be solved by recursive method

var lowestCommonAncestor = function(root, p, q) {
    if(root == null) {return root}
    if(p.val <root.val && root.val> q.val) {
       return lowestCommonAncestor(root.left, p, q);
    }
    if(p.val> root.val && root.val <q.val) {
       return lowestCommonAncestor(root.right, p, q);
    }
    return root;
};

\ [2 ]Add two numbers

Two non-empty linked lists are given and stored in reverse order, and a linked list returned after addition is also stored in reverse order.

/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
}
* /
/*

* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
* /

var addTwoNumbers = function(l1, l2) {
    var node = new ListNode();
    let temp = node, sum, n = 0
    while(l1 || l2) {
        const n1 = l1? l1.val:0
        const n2 = l2? l2.val:0
        sum = n1 + n2 + n
        temp.next = new ListNode(sum%10)
        temp = temp.next
        n = parseInt(sum/10)
        if(l1) l1 = l1.next
        if(l2) l2 = l2.next
    }
    if(n> 0) temp.next = new ListNode(n)
    return node.next
};