LeeCode-刷题日记-Day23

5. 最长回文子串

思路：利用双指针向两端进行遍历。如果两端字符相等则加入子串中。

通过设定开始的左侧指针和右侧指针的值来实现遍历，总长度为奇数、总长度为偶数的回文串。

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let res='';
    let palindrome = (s,l,r)=>{
        while(l>=0&&r<s.length&&s[l]===s[r]){
            l--;
            r++;
        }
        //截取子字符串，第一个参数为开始字段，第二个参数为字符串长度
        return s.substr(l+1,r-l-1);
    }
    for(let i=0;i<s.length;i++){
        //寻找长度为奇数的回文子串
        let s1=palindrome(s,i,i);
        //寻找长度为偶数的回文子串
        let s2=palindrome(s,i,i+1);
        res = res.length>s1.length?res:s1;
        res = res.length>s2.length?res:s2;
    }
    return res;
};

2. 两数相加

思路：将两个指针的每一位分别相加。相加之后，将进位存储在carry中。如果l1或者l2长度不同，将其模拟为后续有无限个0；

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let head=null,tail=null;
    let carry = 0;
    while(l1||l2){
        let n1=l1?l1.val:0;
        let n2=l2?l2.val:0;
        let sum=n1+n2+carry;
        if(!head)
            head=tail=new ListNode(sum%10);
        else{
            tail.next=new ListNode(sum%10);
            tail=tail.next;
        }
        carry=Math.floor(sum/10);
        if(l1)
            l1=l1.next;
        if(l2)
            l2=l2.next;
    }
    if(carry>0)
        tail.next=new ListNode(carry);
    return head;
};

142. 环形链表 II

思路1：双指针，一快一慢。当快慢指针指向同一节点时，表示有环形结构。再从头遍历到目标节点。

思路2：利用哈希表将每个节点存储起来，重复遍历将次数上加。则返回对应节点。

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    if (head === null) {
        return null;
    }
    let slow=head;
    let fast=head;
    while(fast){
        slow=slow.next;
        if(fast.next) fast=fast.next.next;
        else return null;
        if (fast === slow) {
            let ptr = head;
            while (ptr !== slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }
    return null;
};