链表题目练习

序号对应Leedcode题序，解题思路在上篇已提到，这里为具体代码实现，使用JavaScript

1. 单链表反转 206

function reverseList(link) {
    if (!link || !link.next) return link;
    let prev = null; // 反转链表头结点
    let cur = link; // 当前待反转结点
    let next = null; // 待反转下一个节点（存储）
    while(cur) {
        next = cur.next; // 存储
        cur.next = prev; // 指针反转
        prev = cur;
        cur = next;
    }
    // 输出反转链表
    return prev;
}

2. 链表中环的检测 141

function hasCycle(head) {
    while(head) {
        if (head.val === 'tip') {
            return true;
        }else{
            head.val = 'tip';
            head = head.next;
        }
    }
    return false;
}

3. 两个有序的链表合并 21

function mergeTwoLists (l1,l2){
    if (!l1) return l2;
    if (!l2) return l1;
    let result = null;
    if (l1.val > l2.val) {
        result = l2;
        result.next = mergeTwoLists(l1,l2.next);
    }else{
        result = l1;
        result.next = mergeTwoLists(l1.next,l2);
    }
    return result;
}

4. 删除链表倒数第 n 个结点 19

function removeNthFromEnd(head,n){
    // 定义虚拟节点
    let list = new ListNode(-1, head); 
    let slow = list;
    let quick = head;
    while(n--){
        quick = quick.next;
    }
    // 快指针走到底了 删除的是头节点
    if (!quick) {
        return list.next.next;
    }
    while(quick) {
        slow = slow.next;
        quick = quick.next;
    }
    slow.next = slow.next.next;
    return list.next;
}

5. 求链表的中间结点 876

function middleNode(head) {
    let slow = head;
    let quick = head;
    while(quick && quick.next) {
        slow = slow.next;
        quick = quick.next.next;
    }
    return slow;
}