实践总结：一篇搞懂链表——单链表和双指针技巧

单链表

1. 什么是链表

上图就是一个单链表的结构，链表由不同的结点连接在一起组成的，结点不仅包括值，还有指向下一个结点的指针，最后一个节点指向一个None。

# 使用python定义一个节点
class ListNode:
	def __ini__(self,val=0,next=None):
		self.val=val
		self.next=next
1
2
3
4
5

在大多数情况下，使用头结点（第一个结点）来表示整个链表。
例如，在上面的示例中，头结点是 23。访问第 3 个结点的唯一方法是使用头结点中的“next”字段到达第 2 个结点（结点 6）; 然后使用结点 6 的“next”字段，我们能够访问第 3 个结点。

就比如下面这个方法：

def print_head_value(head: Optional[ListNode]) -> None:  
    if head is None:  
        print("The list is empty.")  
    else:  
        print("The value of the head node is:", head.val)  
1
2
3
4
5

刚开始接触链表的时候我也会纳闷，尤其是从java过来的，不知道这个方法的传参怎么传，head: Optional[ListNode]这到底是什么，是传一个结点呢，还是一个链表呢，还是直接传一list。

其实，在链表中头结点不仅表示一个结点，还表示整个链表。

可以通过以下的例子看一下，传入一个[2,4,6,4,9]的列表，是怎么生成一个链表的，其中返回head就包含了整个链表的信息。

def create_linked_list(arr: list) -> Optional[ListNode]:  
    if not arr:  
        return None  
      
    head = ListNode(arr[0])  # 创建头结点  
    current = head  
    for val in arr[1:]:  # 遍历数组剩余元素  
        current.next = ListNode(val)  # 为每个元素创建新结点并链接  
        current = current.next  # 移动到下一个结点  
    return head  # 返回头结点  
1
2
3
4
5
6
7
8
9
10

2. 添加操作 - 单链表

可参考leetcode上的图例解释，点击标题链接就到了。

其实，举个例子就是：把一个链表理解成一列火车，把一节装满货物的车厢（结点），连接到一列火车的不同位置（index），如果连接到火车两端的话，只要把链接勾（就是链表指针）挂在别的车厢，或者被别的链接勾挂上就行，如果连接到中间，那既要被后面的车厢链接勾连接，你还要连接前面的车厢。

3.删除操作-单链表

删除就可以理解为，从一列火车上，拆除不需要的车厢下来。特殊的就是拆除车头和车尾稍微有点不同。

4.设计一个链表

每个人的设计可能不一样，我也是弄了好久才跑通所有的案例，其中遇到最多的一个问题就是，在curr.next之前，一定要判断curr是否可能为None

如果自己没思路写不出来，可以直接先拿过去看和理解，不要一直在那里耗着。

# 定义一个节点
class ListNode:
    def __init__(self,val=0,next=None):
       self.next=next
       self.val=val

class MyLinkedList:
    # 初始化链表
    def __init__(self):
        self.head=None
        self.size=0

    # 获取index位置上的链表节点
    def get(self, index: int) -> int:
        if index<0 or index>=self.size:
            return -1
        
        curr=self.head
        # 根据index遍历到该结点
        for _ in range(index):
            curr=curr.next
        if curr is None:
            return -1
        return curr.val

    # 增加值为val的头节点
    def addAtHead(self, val: int) -> None:
        # 实例化插入的节点
        node =ListNode(val)
        # 将node下一个节点指向头节点
        node.next=self.head
        # 将node置为头节点
        self.head=node
        self.size+=1

    # 增加值为val的尾节点
    def addAtTail(self, val: int) -> None:
        node=ListNode(val)
        curr=self.head
        if curr is None:
            self.head=node
        else:
            # 当curr.next不为None时,遍历到尾节点
            while curr.next:
                curr=curr.next
            curr.next=node
        self.size+=1

    # 在索引index位置插入节点       
    def addAtIndex(self, index: int, val: int) -> None:
        if index<0 or index>self.size:
            return
        node=ListNode(val)
        # 当index等于链表长度时，正好需要插入链表的尾节点，这里要直接return掉，不然self.size会多加1
        if index==self.size:
            self.addAtTail(val)
            return
        elif index==0:
            node.next=self.head
            self.head=node
        else:
            curr=self.head
            # 遍历到index的前一位
            for _ in range(index-1):
                curr=curr.next
            # 将node的下一个节点指向原本在index的节点
            node.next=curr.next
            # 将index的前一位节点指向node,注意上面的和下面的这两个指向不能交换位置执行
            curr.next=node
        self.size+=1

    # 删除索引index处的节点
    def deleteAtIndex(self, index: int) -> None:
        if index<0 or index>=self.size:
            return
        prev=None
        curr=self.head
        if index==0:
            self.head=curr.next
        else:
            # 找出index前一个节点，和index当前节点
            for _ in range(index):
                prev=curr
                curr=curr.next
            prev.next=curr.next
        self.size-=1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

双指针技巧

两种使用双指针技巧的情景：

两个指针从不同位置出发：一个从始端开始，另一个从末端开始；
两个指针以不同速度移动：一个指针快一些，另一个指针慢一些。

在解决环形链表的问题时，经常会用到快慢指针的方法来实现。

下面我们重点讲下，快慢指针的用法。

关于两个指针的速度应该是多少，一个安全的选择是每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。

当它们相遇时，快指针所走的距离是慢指针所走距离的2倍，记住这个结论，有助于理解快慢指针。你可以理解为，相同时间内，快指针是慢指针速度的两倍，所以距离是两倍。

有了以上的概念让我们直接实战，题目详细介绍，可以点击蓝色标题，直接点击链接查看。

1. 环形链表

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

解题思路：
如果是环形链表，那么快慢指针会相遇，没有相遇就说明不是环形指针

代码：

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
           return False
        
        #尽管他们出发的节点不同，但是所用时间相同，因为是慢的走一次快的走一次，所以他们相遇时fast走得距离是慢得的两倍
        slow = head
        fast = head.next

        while slow !=fast:
            if not fast or not fast.next:
                return False
            slow= slow.next
            fast=fast.next.next
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2. 环形链表II

题目：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

解题思路：
这个可能比上一个绕一些，看了下面的代码，你可能有些疑惑，不知道为什么要先用快慢指针找到相遇点，然后换成同一速度的指针，重新走，当它们再次重合，就是链表入环的第一个结点。

这个可能需要你用笔来画一下，并且要知道一个前提，刚开始快指针是慢指针所有距离的2倍。

看下图，理解一下，你就懂了。

代码实现：

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return None
        #尽管他们出发的节点不同，但是所用时间相同，因为是慢的走一次快的走一次，所以他们相遇时fast走得距离是慢得的两倍
        slow=head
        fast=head

        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
            if slow ==fast:
                break
        if not fast or not fast.next:
            return None
        slow=head
        # 当两个结点相同时，就是第一个入环的结点
        while slow!=fast:
            slow=slow.next
            fast=fast.next
        return slow
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3. 相交链表

题目：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

解题思路：
先计算出两个链表的长度，找到两个链表的长度差，遍历两个链表，让长的链表的指针先走过两个链表的长度差，然后，两个链表的指针再同时走，直到相遇，即为交点。
直接看代码

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        lenA=0
        lenB=0

        nodeA=headA
        nodeB=headB

        while nodeA:
            lenA+=1
            nodeA=nodeA.next
        while nodeB:
            lenB+=1
            nodeB=nodeB.next
        
        if lenA>lenB:
            for _ in range(lenA-lenB):
                headA=headA.next
        elif lenB>lenA:
            for _ in range(lenB-lenA):
                headB=headB.next
        
        while headA!=headB:
            headA=headA.next
            headB=headB.next
        return headA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

• 提示

1. 在调用 next 字段之前，始终检查节点是否为空。
   获取空节点的下一个节点将导致空指针错误。例如，在我们运行 fast = fast.next.next 之前，需要检查 fast 和 fast.next 不为空。

2. 仔细定义循环的结束条件。
   运行几个示例，以确保你的结束条件不会导致无限循环。在定义结束条件时，你必须考虑我们的第一点提示。

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

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

解题思路一：
先计算出链表的长度，然后使用长度减去n+1，得到要删除结点的前一位，通过该结点前一位指向该结点的下一位，实现删除该结点。需注意链表长度为1和链表长度相等的情况。
该方法的缺点是需要执行2次遍历遍历操作，一次是计算链表长度，一次是找到要删除结点的前一位结点。

代码实现：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        node=head
        length=0
        # 计算链表的长度
        while node:
            length+=1
            node=node.next
        
        curr=head
        if length<n:
            return head
        elif length==n:
            head=head.next
            return head
        else:
            # 获取删除结点的前一位
            for _ in range(length-n-1):
                curr=curr.next
            # 通过上面的条件判断之后，到这里curr的长度至少等于2，所以不用担心curr或curr.next等于None
            curr.next=curr.next.next
            return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

解题思路二：
使用双指针的思路，实现扫描一遍即可实现该功能。

首先让快指针和慢指针相差n个节点，然后同时移动快指针和慢指针，直到快指针到达链表末尾，此时慢指针就在要删除的第n个结点的前一位。

为什么会有这样的情况，因为始终快指针与慢指针相差n个结点，那么当快指针到达链表结尾的时候，慢指针也是和快指针相差n个结点，那慢指针的位置就能确定在删除节结点的前一位。

代码：

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # 定义两个指针
        first = head
        second = head
        
        # 将第一个指针向前移动 n+1 步
        for _ in range(n + 1):
            if first is None:
                # 如果链表长度不足 n+1，则直接返回头结点的下一个节点
                return head.next
            first = first.next
            
        # 移动第一个和第二个指针直到第一个指针到达链表尾部
        while first is not None:
            first = first.next
            second = second.next
        
        # 删除倒数第 n 个节点,这里不用担心second 或 second.next为None,因为上面的for循环保证second在first之后n+1个，n+1>2
        second.next = second.next.next
        
        return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复杂度分析

点击链接，看双指针的小结

本文参考，leetcode网站上的LeetBook，详见页面：https://leetcode.cn/leetbook/read/linked-list/x6ybqh/