单链表归纳总结

常见应用场景：一些缓存场景，如LRU缓存淘汰算法

单链表升级版：双向链表、循环链表

小技巧

技巧一：利用哨兵（头节点）简化实现难度

如果我们要在链表中进行插入操作时，当链表为空时和当链表不为空时，操作是不同的。如果我们要在链表中进行删除操作时，当要删除的节点是最末节点时和当要删除的节点不是最末节点时，操作是不同的。

针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。这样代码实现起来就会很繁琐，不简洁，而且也容易因为考虑不全而出错，使用哨兵（头节点）可以帮助我们统一操作。

如果我们引入哨兵结点，在任何时候，不管链表是不是空，head指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。

因为哨兵结点一直存在，所以插入第一个结点和插入其他结点，删除最后一个结点和删除其他结点，都可以统一为相同的代码实现逻辑了。

技巧二：重点留意边界条件处理

如果链表为空时，代码是否能正常工作？

如果链表只包含一个结点时，代码是否能正常工作？

如果链表只包含两个结点时，代码是否能正常工作？

代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

技巧三：举例画图，辅助思考

配套练习题

一、单链表反转

解法对应于Leetcode 206 单链表反转

思路：在遍历单链表的同时反转指针，从而达到使单链表逆序的功能。
注意事项：要在纸上简单画一下过程，理顺一下每一步的顺序，不要丢失指针即可。
方法：首先新建null节点为node，并让一个游标cursor指向head，因为我们需要反转指针，cursor.next = node如果先执行了的话，就会造成丢失指针，故需要有一个临时的nextNode保存当前处理节点的下一个节点，并在最后使得cursor = nextNode

// Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
// Output: 5 -> 4 -> 3 -> 2 -> 1 -> NULL
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
    let node = null
    let cursor = head
    while (cursor != null) {
        let nextNode = cursor.next
        cursor.next = node
        node = cursor
        cursor = nextNode
    }
    return node
};

二、链表中环的检测

解法对应于Leetcode 141 链表中环的检测

解法一、快慢指针法

思路：快指针跑在前头，慢指针在后，如果存在环的话，快指针就一定能追上慢指针。
注意事项：while的条件，因为快指针跑的快，所以主要是判断fast的临界。只有当fast和fast.next均不为null时，才不会发生TypeError: Cannot read property 'next' of null之类的错误

// Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
// Output: 5 -> 4 -> 3 -> 2 -> 1 -> NULL
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
    let node = null
    let cursor = head
    while (cursor != null) {
        let nextNode = cursor.next
        cursor.next = node
        node = cursor
        cursor = nextNode
    }
    return node
};

解法二、Set集合映射法

思路：新建一个Set，遍历链表，判断Set是否含有当前处理的节点，若有，说明之前已经遇到过，有环。否则就说明是新的节点，那么就add到Set中，然后继续下一个节点

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
    let set = new Set()
    while (head != null) {
        if (set.has(head)) {
            return true
        }
        set.add(head)
        head = head.next
    }
    return false
};

三、两个有序的链表合并

解法对应于Leetcode 21 两个有序的链表合并

解法一、新建链表法

思路：新的链使用哨兵guard，然后l1与l2反复比较头节点大小，小的就摘除，接到新的链后面。相等的话就l1先l2后，都接到新的链后面。当其中一条链为空，就把另外一条链剩下的都接到新链后即可。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
    if (!l1) return l2
    if (!l2) return l1
    let guard = new ListNode(null)
    let cursor = guard
    while (l1 && l2) {
        if (l1.val < l2.val) {
            cursor.next = l1
            l1 = l1.next
        } else if (l1.val > l2.val) {
            cursor.next = l2
            l2 = l2.next
        } else {
            cursor.next = l1
            l1 = l1.next
            cursor = cursor.next
            cursor.next = l2
            l2 = l2.next
        }
        cursor = cursor.next
    }
    cursor.next = l1 || l2
    return guard.next
};

解法二、原地合并法（递归）

递归指的是把问题分解成为规模更小的、具有与原问题有着相同解法的问题。

递归特性一：必须有一个明确的结束条件

递归特性二：每次递归都是为了让问题规模变小

递归特性三：层次过多会导致栈溢出，且效率不高

思路：使用递归的方法，明确结束条件是当其中一条链为空时，递归就会结束。每次递归都使得head所在的链少一个节点，进而使问题规模变小

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
    if (!l1) return l2
    if (!l2) return l1

    let head = l1.val < l2.val ? l1 : l2
    let left = l1.val < l2.val ? l2 : l1

    head.next = mergeTwoLists(head.next, left)

    return head
};

四、删除链表倒数第 n 个结点

解法对应于Leetcode 19 删除链表倒数第 n 个结点

解法一、快慢指针法 - （一趟搞定）

思路：为了方便处理只有一个节点的情况，我们引入头指针guard。让快慢指针fast & slow均指向guard，然后看传入的n的值，n为多少，则快指针就先走几步，由于我们引入了头节点，所以快指针相应的要多走一步，故为n+1。接下来就是快慢指针同时往后走，直到快指针走到头。我们画图可以发现，当前的slow处于待删除节点的前方，我们接下来就使用slow.next = slow.next.next即可删除对应的节点了，之后再返回头指针的next即可。
注意事项：引入头指针后，fast应先走n+1步。做链表题一定要同时画一画草图，思路更清晰

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
    let guard = new ListNode(null)
    guard.next = head
    let fast = guard
    let slow = guard
    for (let i = 0; i < n + 1; i++) {
        fast = fast.next
    }
    while (fast) {
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
    return guard.next
};

解法二、快慢指针法 - （两趟搞定）

思路：同样的，哨兵guard头节点是为了处理只有一个节点时的特殊情况。第一遍先从头遍历完链表，计算出从head走到链表结尾需要的步数length。然后用length-n算出从head要到倒数第n个节点前需要的步数。那么如果是从guard开始走length - n步就可以走到待删除节点的前面，然后使用cursor.next = cursor.next.next即可

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
    let guard = new ListNode(null)
    guard.next = head
    let cursor = head
    let length = 0
    while (cursor) {
        length++
        cursor = cursor.next
    }
    cursor = guard
    length -= n
    while (length) {
        length--
        cursor = cursor.next
    }
    cursor.next = cursor.next.next
    return guard.next
};

五、求链表的中间结点

解法对应于Leetcode 876 求链表的中间结点

解法一、快慢指针法

思路：这个很简单，就没什么好说的了。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function (head) {
    let fast = head
    let slow = head
    while (fast && fast.next) {
        fast = fast.next.next
        slow = slow.next
    }
    return slow
};

小技巧

技巧一：利用哨兵（头节点）简化实现难度

技巧二：重点留意边界条件处理

技巧三：举例画图，辅助思考

配套练习题

一、单链表反转

二、链表中环的检测

解法一、快慢指针法

解法二、Set集合映射法

三、两个有序的链表合并

解法一、新建链表法

解法二、原地合并法（递归）

四、删除链表倒数第 n 个结点

解法一、快慢指针法 - （一趟搞定）

解法二、快慢指针法 - （两趟搞定）

五、求链表的中间结点

解法一、快慢指针法