双指针

简介

双指针是一种思想或一种技巧并不是特别具体的算法。

具体就是用两个变量动态存储两个结点，来方便我们进行一些操作。通常用在线性的数据结构中。

特别是链表类的题目，经常需要用到两个或多个指针配合来记忆链表上的节点，完成某些操作。

常见的双指针方式

1.同速指针：链表上两个指针，一个先出发，另一个后出发并以相同的速度跟随。

  • 求链表的逆：通过临时指针让双指针同步前行。
  • 求链表倒数第k个元素：先让其中一个指针向前走k步，接着两个指针以同样的速度一起向前进，直到前面的指针走到尽头了，则后面的指针即为倒数第k个元素。

2.快慢指针：链表上两个指针从同一节点出发，其中一个指针前进速度比另一个指针快（比如，是另一个指针的两倍）。

  • 计算链表的中点：快慢指针从头节点出发，每轮迭代中，快指针向前移动两个节点，慢指针向前移动一个节点，最终当快指针到达终点的时候，慢指针刚好在中间的节点。
  • 判断链表是否有环：快慢指针从头节点出发，如果链表中存在环，两个指针最终会在环中相遇。
  • 求链表中环的长度：只要相遇后一个不动，另一个前进直到相遇算一下走了多少步就好。

案例1：反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。（同步指针解决）

示例 1：

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or head.next is None:
            return head
        p1 = head
        p2 = None
        
        while p1:
            temp = p1.next
            p1.next = p2
            p2 = p1
            p1 = temp
        
        return p2
>> 32 ms	15.5 MB

案例2：删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。（同速指针）

示例 1：

1
2
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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: ListNode, n: int) -> ListNode:
        p1, p2 = head, head
        # 先让p1先走n步
        while n > 0:
            p1 = p1.next
            n -= 1
            
        if p1 is None:
            return p2.next
        while p1.next:
            p2 = p2.next
            p1 = p1.next
        p2.next = p2.next.next
        
        return head
>> 	36 ms	14.9 MB