# Algorithm Small Daily-02

Posted May 27, 2020 • 3 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
};
```