《双指针可以解决的六类问题》

• 获取倒数第k个元素：
  设有两个指针 p 和 q，初始时均指向头结点。首先，先让 p 沿着 next 移动 k 次。此时，p 指向第 k+1个结点，q 指向头节点，两个指针的距离为 k 。然后，同时移动 p 和 q，直到 p 指向空，此时 q 即指向倒数第 k 个结点。

• 获取中间位置的元素：
  也是一快一慢，快两格，慢一格，快走到结尾时，慢在最中间（n为奇数时） or 慢在第二个节点（n为偶数时，判断语句while fast and fast.next）一定要是and ！！

• 判断链表是否存在环：
  龟兔赛跑，兔子每次跳两格，龟每次一格，兔子先进入环，龟后进入，如果兔子后面等于龟，证明有环。

• 判断环的长度：
  快慢指针相遇后继续移动，直到第二次相遇。两次相遇间的移动次数即为环的长度。

• 相交链表:
  找链表A和链表B的公共节点，返回剩余链表。一个指针指向A，一个指针指向B，两个指针都遍历a+b-c次，规定先遍历自己，在遍历对方的b-c，最后两个节点重合的时候，指向的就是相交节点。

• 反转链表：
  力扣206题
  双指针pre 和 cur，一个在前一个在后，初始设置，修改next方向，循环终止条件，返回。要注意的就是需要有一个tmp，暂存下一个节点 以及 把暂存的tmp赋值给别人的一个操作。

# 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:
        cur = None
        pre = head
        # t = head
        while pre:
            tmp = pre.next
            pre.next = cur
            cur = pre
            pre = tmp
            # pre = t.next
        return cur
        

• 其他：
  移动零 力扣283题

最后

以上就是饱满外套为你收集整理的《双指针可以解决的六类问题》的全部内容，希望文章能够帮你解决《双指针可以解决的六类问题》所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。