[数据结构与算法]每日三道题

环形链表

给定一个链表，判断链表中是否有环。

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

思路：快慢指针，只要有个转，迟早会遇到

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let slow=head;
    let fast=head;
    while(fast!=null&& fast.next!=null){
        slow=slow.next;
        fast=fast.next.next;
        if (slow == fast)
            return true;
        
    }
    return false;
    
};

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

输入：head = [1,2,2,1]
输出：true

思路：简单点，就是把链表转换为其他物理结构，例如数组、栈等，

var isPalindrome = function(head) {
    if(!head|| !head.next){
        return true;
    }
    let arr=[]
    while(head){
        arr.push(head.val);
        head=head.next ;
    }
    let left=0;
    let right=arr.length-1;
    while(left<right){
        if(arr[left]!==arr[right]){
            return false;
        }
      left++;
      right--;
    }
 return true;
};

合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

思路：递归是个好主意，不断找最小，执行

var mergeTwoLists = function(l1, l2) {
    if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;
    if(l1.val<l2.val){
        //代表用li,然后l1的下一个指向
        l1.next=mergeTwoLists(l1.next,l2)
        reurn l1;
    }else{
        l2.next=mergeTwoLists(l1,l2.next)
        reurn l2;
    }

};