理论基础

与数组相比，链表在内存中的存储是不连续的。

链表通过指针来连接元素与元素，而数组则是在内存中开辟一块完整的、连续的空间进行存储。

数组的查找比较方便、但是插入和删除比较复杂。此外，数组的大小是固定的，一旦确定下来，后期难以修改。

虽然链表的查询比较复杂，但是插入和删除比较简单。此外，与数组相比，扩展性更高。

移除元素（leetcode no.203）

删除链表中等于给定值val的所有节点。

唯一难点：当头节点需要删除时，代码如何书写以具备可行性。

方法1（比较简单，参考[1]）：设置一个虚拟头节点，因此对于头节点的操作也是等于中间节点的操作。

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        virtual_head = ListNode()
        virtual_head.next = head
        tmp = virtual_head
        while tmp.next is not None:
            if tmp.next.val == val:
                tmp.next = tmp.next.next
            else:
                tmp = tmp.next
        return virtual_head.next

方法2：代码稍微复杂，需要在头节点增加一些额外的代码控制。

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        tmp = head
        pre = None
        while tmp is not None:
            if tmp.val == val:
                if pre is None:
                    head = tmp.next
                else:
                    pre.next = tmp.next
                tmp = tmp.next
                continue
            pre = tmp
            tmp = tmp.next
        return head

设计链表（leetcode no.707）

实现链表的增删查改功能。

其中按照[1]中的思路，通过一个虚拟头节点，即可让代码的复杂度下降。

不过需要注意的是，在使用tmp.next.val时，需要事先判断tmp.next是否为None

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

class MyLinkedList:

    def __init__(self):
        self.list = ListNode(0)


    def get(self, index: int) -> int:
        tmp = self.list
        for _ in range(index):
            tmp = tmp.next
            if tmp is None:
                return -1
        if tmp.next is not None:
            return tmp.next.val
        return -1

    def addAtHead(self, val: int) -> None:
        node = ListNode(val)
        node.next = self.list.next
        self.list.next = node

    def addAtTail(self, val: int) -> None:
        tmp = self.list
        while tmp.next is not None:
            tmp = tmp.next
        tmp.next = ListNode(val)

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0:
            self.addAtHead(val)
        tmp = self.list
        for _ in range(index):
            tmp = tmp.next
            if tmp is None:
                return
        node = ListNode(val)
        node.next = tmp.next
        tmp.next = node

    def deleteAtIndex(self, index: int) -> None:
        if index < 0:
            return
        tmp = self.list
        for _ in range(index):
            tmp = tmp.next
            if tmp == None:
                return 
        if tmp.next is not None:
            tmp.next = tmp.next.next

反转链表（leetcode no.206）

对链表进行反转，比如：

1 -> 2 -> 3 -> 4 -> 5

反转后为：

5 -> 4 -> 3 -> 2 -> 1

一般可以直接反转或者通过递归进行反转。

直接反转需要记住在反转中的操作步骤（在一个while循环下操作）：

1. 首先通过一个after变量保存curr.next
2. 对节点进行反转
3. 将当前节点设置为pre
4. 将curr更新为after

代码中最后返回pre是因为curr最后因为curr=after，因此其为None。所以返回pre。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        curr = head
        pre = None
        while tmp is not None:
            after = curr.next
            curr.next = pre
            pre = curr
            curr = after
        return pre

递归法则不需要考虑节点的变量，我们只需要在每一次递归中，将curr.next 设置为 pre，而进行下一次递归则为curr，curr.next（这个curr.next指的是原先curr.next，需要事先存储）。

此外，在递归的过程中，需要考虑最后的结束，当curr为None时，表示没法再进行递归，因此需要返回pre。

具体代码为：

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        def recr(pre, curr):
            if curr is None:
                return pre
            after = curr.next
            curr.next = pre
            return recr(curr, after)
        return recr(None, head)

两两交换链表中的节点（leetcode no.24）

两两交换节点，如果节点的数量只有单数个，那么最后一个节点不需要交换。在节点的交换过程中，需要注意保存，以及节点的交换顺序。总体思路不难，但是需要牢记顺序。

（下面的图示中，虚线为本次步骤中去掉的线，红色的线是新增的，均是对node.next进行操作）。

步骤1：

步骤2：

步骤3：

步骤4：开启下一次循环

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        virtual_head = ListNode(next=head)
        tmp = virtual_head
        while tmp.next is not None and tmp.next.next is not None:
            node1 = tmp.next
            node2 = node1.next
            node1.next = node2.next  # 步骤1
            node2.next = node1       # 步骤2
            tmp.next = node2         # 步骤3
            tmp = node1              # 步骤4

        return virtual_head.next

删除链表的倒数第$nn$个节点（leetcode no.9）

由于链表为单向链表，因此无法到达最后一个节点后，再往前走$nn$个节点。虽然可以通过蛮力法解决该问题，但是蛮力法的时间复杂度过高。

有没有$O(n)O(n)$时间复杂度的算法？这可以考虑双指针，fast指针比slow指针多走$nn$步，那么当fast指针走到最后时，slow指针指向的位置则就是要删除的节点。

此外，与链表的其他问题一致，由于初始节点的特殊性（代码构造复杂），因此可以通过一个虚拟节点，将初始节点也变为链表中的一部分，这并不会对最终结果产生影响，最终只需要返回虚拟节点的next即可。

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        virtual_node = ListNode(next=head)
        slow = virtual_node
        fast = virtual_node
        for _ in range(n):
            fast = fast.next
        while fast.next is not None:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return virtual_node.next

链表交叉（leetcode 面02.07）

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

如果两个链表交叉，那么他们的尾部是一样的。这意味着，长链条前面的多个节点是不会产生交叉点的。因此这些点需要排除。所以这道题的思路应该是：

1. 先找出两条链表的长度
2. 长链表先走和短链表一样的长度
3. 长链表和锻炼表一起迭代查找，当两者对象相等时，则返回，否则最后返回null。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        def getLength(head: ListNode):
            length = 1
            tmp = head
            while tmp:
                length += 1
                tmp = tmp.next
            return length
        len_a = getLength(headA)
        len_b = getLength(headB)
        if len_a > len_b:
            long_head = headA
            short_head = headB
            gap = len_a - len_b
        else:
            long_head = headB
            short_head = headA
            gap = len_b - len_a
        for _ in range(gap):
            long_head = long_head.next
        while long_head is not None:
            if long_head == short_head:
                return long_head
            long_head = long_head.next
            short_head = short_head.next
        return None

环形链表（leetcode no.142）

判断一个链表是否存在环。

如果链表存在环，那么两个速度不一样的指针最终会相交于一点。

（下面的思路为代码随想录 (programmercarl.com)内容，其中，某些地方由于初看该解释没搞懂，后期搞懂。）

因此，可以使用两个指针分别为fast和slow来寻找环是否存在。假设环是这样子的，其中黄色点为相交的点。

我们如果假设环的长度为$Y+ZY+Z$，而进环前的链表长度为$XX$。因此，slow节点走过的长度为$X+YX+Y$，而fast节点走过的长度为$X+Y+n\times (Y+Z)X+Y+n\backslash times(Y+Z)$。

推断1：slow节点在环内所走距离不超过一圈。

证明：这个以反证法为例，如果slow在环中走超过1圈，由于fast的速度是slow的两倍，所以fast在环中走的距离超过2圈。在此情况下，fast节点超过slow节点一圈或一圈以上的路程。由于fast节点更快，因此可以假定slow节点暂停等待fast节点。由于fast节点超过slow节点1圈，因此，fast节点可以在一圈内追上slow节点。这与前面的fast节点在圈内多走一圈不符合，因此假设错误，推翻假设。假设的反命题成立。

由于fast的速度是slow的两倍，因此有：

调整后，有：

这里的$Y+ZY+Z$为圆圈的长度，当这一项忽略时，有

这意味着，如果在起始点和fast与slow的相交点同时放一个指针，以同样的速度往前走，那么两指针相交的位置为圆环的入口（从下面的图也可以看出结果）。由于$Y+ZY+Z$为圆圈的长度，因此该项是否添加对环的起始位置并无影响。

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                tmp1 = head
                tmp2 = slow
                while tmp1 != tmp2:
                    tmp1 = tmp1.next
                    tmp2 = tmp2.next
                return tmp1
        return None

总结

• 由于链表的操作不同，因此需要用tmp进行存储，否则容易丢失链表
• 当链表头部操作复杂时，可以试试虚拟头节点，最终返回虚拟头节点的下一个位置。

参考网址：

[1] 代码随想录 (programmercarl.com)