148.排序链表

题目描述：在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序
思路分析：用归并排序的思路对链表递归分裂。分裂的过程使用快慢指针（双指针法），获取链表的中间节点根据中间节点，分割成两个小链表递归执行上一步，直到小链表中只有一个节点。之后再递归合并排序。

let sortList = function(head) {
    return mergeSortRec(head)
}

// 归并排序
// 若分裂后的两个链表长度不为 1，则继续分裂
// 直到分裂后的链表长度都为 1，
// 然后合并小链表
let mergeSortRec = function (head) {
    if(!head || !head.next) {
        return head
    }

    // 获取中间节点
    let middle = middleNode(head)
    // 分裂成两个链表
    let temp = middle.next
    middle.next = null
    let left = head, right = temp
    // 继续分裂（递归分裂）
    left = mergeSortRec(left)
    right = mergeSortRec(right)
    // 合并两个有序链表
    return mergeTwoLists(left, right)
}

// 获取中间节点
// - 如果链表长度为奇数，则返回中间节点
// - 如果链表长度为偶数，则有两个中间节点，这里返回第一个
let middleNode = function(head) {
    let fast = head, slow = head
    while(fast && fast.next && fast.next.next) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
}

// 合并两个有序链表
let mergeTwoLists = function(l1, l2) {
    let preHead = new ListNode(-1);
    let cur = preHead;
    while(l1 && l2){
        if(l1.val < l2.val){
            cur.next = l1;
            l1 = l1.next;
        }else{
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    cur.next = l1 || l2;
    return preHead.next;
}

141.环形链表

题目描述：给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

var hasCycle = function(head) {
    let fast = head;
    let slow = head;
    while (fast !== null && fast.next !== null) {
        fast = fast.next.next;
        slow = slow.next;
        if (slow === fast) {
            return true;
        }
    }
    return false;
};

142.环形链表II

题目描述：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
思路分析：

image.png

var detectCycle = function(head) {
    let fast = head;
    let slow = head;
    while (fast !== null && fast.next !== null) {
        fast = fast.next.next;
        slow = slow.next;
        if (slow === fast) {
            slow = head;
            while (slow !== fast) {
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
    }
    return null;
    
};

160.相交链表

题目描述：编写一个程序，找到两个单链表相交的起始节点

var getIntersectionNode = function(headA, headB) {
    let p1 = headA;
    let p2 = headB;
    while (p1 && p2) {
        if (p1 === p2) {
            return p1;
        }
        p1 = p1.next;
        p2 = p2.next;
    }
    //若A是短链表，B是长链表  
    if (p1 === null) {
        p1 = headB;
        while (p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        //此时headB到p1的距离为两链表之差
        //让p2从短链表A从头遍历，p1在长链表B的原处继续遍历
        //二者相等点即为公共节点
        p2 = headA;
        while (p1 !== p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
    //若B是短链表，A是长链表
    else {
        p2 = headA;
        while (p1) {
            p1 = p1.next;
            p2 = p2.next;
        }
        //此时headA到p2的距离为两链表之差
        //让p1从短链表B从头遍历，p2在长链表A的原处继续遍历
        //二者相等点即为公共节点
        p1 = headB;
        while (p1 !== p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
};

234.回文链表

题目描述：请判断一个链表是否为回文链表
思路：用快慢指针寻找出链表中点，在遍历时将前半部分存入一个栈，遍历后半部分时依次弹出栈的元素，比较是否相等。

var isPalindrome = function(head) {
    let fast = head;
    let slow = head;
    const stack = [];
    while (fast !== null && fast.next !== null) {
        fast = fast.next.next;
        stack.push(slow.val);
        slow = slow.next;
    }
    // 处理链表长度只有 1 的情况,返回true
    if (!stack.length) {
        return true;
    }
    //若链表长度为奇数，slow指针后移一位
    if (fast) {
        slow = slow.next;
    }
    // 通过比较后半段链表的值和前半段链表的值是否相等从而判断是否为回文链表
    while (slow) {
        let temp = stack.pop();
        if (temp !== slow.val) {
            return false;
        }
        slow = slow.next;
    }
    return true;
};

21.合并两个有序链表

递归版本：

var mergeTwoLists = function(l1, l2) {
    if (l1 === null) {
        return l2;
    } else if (l2 === null) {
        return l1;
    } else if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};

迭代版本：

var mergeTwoLists = function(l1, l2) {
    const prehead = new ListNode(-1);
    let p = prehead;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            p.next = l1;
            l1 = l1.next;
        } else {
            p.next = l2;
            l2 = l2.next;
        }
        p = p.next;
    }
    // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
    p.next = l1 === null ? l2 : l1;
    return prehead.next;
};