初级算法 链表

删除链表中的节点

请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。

题目数据保证需要删除的节点 不是末尾节点 。

var deleteNode = function(node) {
    node.val = node.next.val
    node.next = node.next.next
};

删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

var removeNthFromEnd = function(head, n) {
    let k = n ;
    let dummy  = new ListNode(-1)
    dummy.next = head
    let slow = dummy.next
    let fast = dummy.next;
    let prev = slow
    while(k > 0){
        fast = fast.next
        k--
    }
    while(fast != null){
        fast = fast.next
        prev = slow
        slow = slow.next
    }
    if(slow == head){
        head = slow.next
    }else {
       prev.next = prev.next.next
    }
    return head
};

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

var reverseList = function(head) {
    let list = []
    let pointer = head
    while(pointer){
        list.push(pointer)
        pointer = pointer.next
    }
    let dummy = new ListNode(-1)
    let curr = dummy
    while(list.length){
        let node =  list.pop()
        node.next = null
        curr.next = node
        curr = node
    }
    return dummy.next
};

var reverseList = function(head) {
    reverse(head)
    function reverse(node) {
        if (node.next == null) return node;
        let last = reverse(node.next);
        node.next.next = node;
        node.next = null;
        return last;
    }
}

合并两个有序链表

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

var mergeTwoLists = function(list1, list2) {
    let p1 = list1
    let p2 = list2
    let dummy = new ListNode(-1)
    let p = dummy
    while(p1 !=null && p2 !=null){
            if(p1.val < p2.val){
                p.next = p1
                p1 = p1.next
            }else {
                p.next = p2
                p2 = p2.next
            }
            p = p.next
    }
    if(p1 != null){
        p.next = p1
    }
    if(p2 != null){
        p.next = p2
    }
    return dummy.next
};

回文链表

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

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

有环链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

const hasCycle = function(head) {
    let slow = fast = head
    while(fast != null && fast.next != null ){
        slow = slow.next
        fast = fast.next.next
        if( slow == fast ) return true

    }
    return false
};