算法：双指针

用户3578099

发布于 2022-04-18 16:24:13

3070

发布于 2022-04-18 16:24:13

文章被收录于专栏：AI科技时讯AI科技时讯

双指针

双指针是一种思想或一种技巧并不是特别具体的算法。具体就是用两个变量动态存储两个结点，来方便我们进行一些操作。通常用在线性的数据结构中。

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

常见的双指针方式

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

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

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

•计算链表的中点：快慢指针从头节点出发，每轮迭代中，快指针向前移动两个节点，慢

指针向前移动一个节点，最终当快指针到达终点的时候，慢指针刚好在中间的节点

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

双指针常用于线性结构：链表，数组

例题

151.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例：

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

输入：head = [1,2]
输出：[2,1]

输入：head = []
输出：[]

解题思路：

•方法1：遍历一遍使用列表存储元素，再进行反转，再遍历一遍将元素串起来

•方法2：通速指针方法，两个指针一前一后，使用中间变量保存下一个节点，之后再进行移动赋值

python实现

# 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 head is None or head.next is None:
            return head

        p1 = None
        p2 = head
        while p2:  # 画图即可
            tmp = p2.next
            p2.next = p1
            p1 = p2
            p2 = tmp
        return p1  # p1在p2的前面，p2已经是末尾None

c++实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* p1 = nullptr;
        ListNode* p2 = head;
        while(p2 != nullptr)
        {
            ListNode* tmp = p2->next;
            p2->next = p1;
            p1 = p2;
            p2 = tmp;
        }
        return p1;
    }
};

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

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

示例 1：

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

输入：head = [1], n = 1
输出：[]

输入：head = [1,2], n = 1
输出：[1]

解题思路：

•方法1：遍历一遍保存链表每个节点的val，转成列表之后，删除倒数第N个节点的值，再遍历一遍进行串联即可•方法2：快慢指针，一个先不动，一个先往前走n步，然后再两个一起走动，直到先走的指针到达末尾，则慢指针到达末尾第n-1个元素，再设置该处的元素x.next = x.next.next

python实现

# 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 = head
        p2 = head
        for i in range(n):  # 快指针先走n步
            p2 = p2.next

        if not p2:  # 如果已经走到末尾了，则表明应该删除头结点
            return p1.next

        while p2.next:   # 这里是P2.next， 需要往前退一步
            p1 = p1.next
            p2 = p2.next

        p1.next = p1.next.next
        return head

c++实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* p1 = head;
        ListNode* p2 = head;
        while(n)
        {
            p2 = p2->next;
            n--;
        }

        if(p2==nullptr)
        {
            return p1->next;
        }

        while(p2->next)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        p1->next = p1->next->next;

        return head;
    }
};

118.环形链表

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

解题思路：

•方法1：遍历并存储节点到一个哈希表中，节点作为key，遍历时候如果发现该节点已经在哈希表中则表明有环•方法2：使用快慢指针，一个每次走一步，一个每次走两步，如果两者有重叠的话，则表明存在环路。

python实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return False

        p_slow = head
        p_fast = head
        while p_fast and p_fast.next:  # 条件要增加一个判断p_fast是否是节点以及其下一个是否为节点
            p_slow = p_slow.next
            p_fast = p_fast.next.next
            if p_slow == p_fast:
                return True
        return False

c++实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
       if(head == nullptr || head->next == nullptr)
       {
           return false;
       }

       ListNode* p_slow = head;
       ListNode* p_fast = head;
       while(p_fast && p_fast->next)
       {
           p_slow = p_slow->next;
           p_fast = p_fast->next->next;  // 走两步
           if(p_slow == p_fast)
           {
               return true;
           }
       }
       return false;
    }
};

71.删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

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

解题思路：

•方法1：使用栈的思想，如果后面入的元素与栈顶元素相同，就略过该元素，继续遍历•方法2：双指针，一前一后，后面的指针与前面的指针元素进行比较，如果是相同值，则后指针继续往后走。如果不相同，则前指针移动到后指针位置，后指针也往后移动一位。

python实现

跟前面比

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head

        pre_node = head
        cur_node = head.next
        while cur_node:  # 要一直比较到末尾，这里用cur_node 不是cur_node.next
            if pre_node.val == cur_node.val:  # 与前面的节点进行相比
                pre_node.next = cur_node.next
                cur_node = cur_node.next
            else:
                pre_node = cur_node
                cur_node = cur_node.next
        return head

c++实现

跟后面比

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==nullptr || head->next==nullptr)
        {
            return head;
        }

        ListNode* cur = head;
        while(cur->next != nullptr)
        {
            if(cur->val == cur->next->val)  // 与后面的元素进行相比较，如果后面的元素与cur元素相同，则略过该后面的元素
            {
                cur->next = cur->next->next;
            }
            else  // 如果不相同，此时cur往后挪一个节点
            {
                cur = cur->next;
            }
        }
        return head;
    }
};

125.排序链表

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

示例 1：

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

示例 2：

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

示例 3：

输入：head = []
输出：[]

解题思路：

•方法1：遍历并使用列表保存，对列表进行排序，再遍历一遍将元素串起来•方法2：使用快慢指针将链表截断为两部分，使用递归的方法对子链表进行排序，再使用合并单链表的方式两两串联起来。递归排序的终止条件是链表的节点个数小于或等于，即当链表为空或者链表只包含1个节点时，不需要对链表进行拆分和排序

python实现

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        def sortFunc(head: ListNode, tail: ListNode) -> ListNode:
            if not head:
                return head
            if head.next == tail:
                head.next = None  # 断开 分为一个个节点
                return head
            slow = fast = head
            while fast != tail:
                slow = slow.next
                fast = fast.next
                if fast != tail:
                    fast = fast.next
            mid = slow
            return merge(sortFunc(head, mid), sortFunc(mid, tail))

        def merge(head1: ListNode, head2: ListNode) -> ListNode:
            dummyHead = ListNode(0)
            temp, temp1, temp2 = dummyHead, head1, head2
            while temp1 and temp2:
                if temp1.val <= temp2.val:
                    temp.next = temp1
                    temp1 = temp1.next
                else:
                    temp.next = temp2
                    temp2 = temp2.next
                temp = temp.next
            if temp1:
                temp.next = temp1
            elif temp2:
                temp.next = temp2
            return dummyHead.next

        return sortFunc(head, None)

c++实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return sortFunc(head, nullptr);
    }

    ListNode* sortFunc(ListNode* head, ListNode* tail)
    {
        if(head==nullptr)
        {
            return head;
        }

        if(head->next == tail)
        {
            head->next = nullptr;  // 断开
            return head;
        }

        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != tail)
        {
            slow = slow->next;
            fast = fast->next;
            if(fast != tail)
            {
                fast = fast->next;
            }
        }

        ListNode* mid = slow;
        return merge(sortFunc(head, mid), sortFunc(mid, tail));
    }

    ListNode* merge(ListNode* head1, ListNode* head2)
    {
        ListNode* dummyHead = new ListNode(0);
        ListNode* tmp = dummyHead;
        ListNode* tmp1 = head1;
        ListNode* tmp2 = head2;
        while(tmp1!=nullptr && tmp2 != nullptr)
        {
            if(tmp1->val <= tmp2->val)
            {
                tmp->next = tmp1;
                tmp1 = tmp1->next;
            }
            else
            {
                tmp->next = tmp2;
                tmp2 = tmp2->next;
            }

            tmp = tmp->next;
        }

        if(tmp1 != nullptr)
        {
            tmp->next = tmp1;
        }
        else if(tmp2 != nullptr)
        {
            tmp->next = tmp2;
        }
        return dummyHead->next;
    }
};

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2022-03-24，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法