双指针法运用

                     

贡献者: 叶燊Leafshen

预备知识 双指针算法
  • 本文处于草稿阶段。
  • 请不要占用他人词条不作为 缺少一些图片解释,待有缘人吧,例 2 有时间再更

例 1 快慢指针——链表中点

   给定一个头结点为 h 的非空单链表,返回链表的中间结点。

   如果有两个中间结点,则返回第二个中间结点。

   ex.1

   输入:[1,2,3,4,5]

   输出:此列表中的结点 3 (序列化形式:[3,4,5]) 返回的结点值为 3。

   ex.2

   输入:[1,2,3,4,5,6]

   输出:此列表中的结点 4 (序列化形式:[4,5,6])

1. 解

方法一:

   数组

   我们最常做的就是遍历法了,简单,暴力,将遍历到的元素依次放入数组 A 中。如果我们遍历到了 n 个元素,那么链表及数组的长度也为 n,对应的中间节点即为 A[n/2]

   下面整理的为几种语言的部分代码:

def middlenode ():
    A = [h]
        while A[-1].next:
            A.append(A[-1].next)
    return A[len(A) // 2]
python 如上
public:
    ListNode* middlenode(ListNode* head) 
    {
        vector<ListNode*> A = {h};
        while (A.back()->next != NULL)
            A.push_back(A.back()->next);
        return A[A.size() / 2];
    }
C++见上

   时间复杂度:O(N),其中 N 是给定链表中的结点数目。

   空间复杂度:O(N),即数组 A 用去的空间。

方法二:

   单指针法

   方法一可以进行空间优化,比如省去数组 A。

   我们可以对链表进行两次遍历。第一次遍历时,我们统计链表中的元素个数 N;第二次遍历时,我们遍历到第 N/2 个元素(链表的首节点为第 0 个元素)时,返回该元素即可。

   相当于,方法一我们拿刻度瓶装,方法二我们用数豆子的方法

def middlenode():
    n, a = 0, h
    while a:
        n += 1
        a = a.next #第一次
    b, a = 0, h
    while b < n // 2:
        b += 1
        a = a.next #第二次
    return a
python 如上
public ListNode middlenode() 
    {
        int n = 0;
        ListNode a = h;
        while (a != null) 
        {
            ++n;
            a = a.next;
        }
        int b = 0;
        a = h;
        while (b < n / 2) 
        {
            ++b;
            a = a.next;
        }
        return a;
    }
java 如上

   时间复杂度:O(N),其中 N 是给定链表的结点数目。

   空间复杂度:O(1),常数空间存放变量和指针。

方法三:

   快慢指针法

   继续优化,用两个速度不同的指针 slow 与 fast 一起遍历链表。速度不同产生位移之差,于是,我们让慢爷爷一次走一步,快小伙一次走两步。不妨试试,你会发现,当 fast 走到末尾时,slow 恰在中间。

   所以:

def middlenode():
    slow = fast = h
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow
python
public:
    ListNode* middlenode(ListNode* h) 
    {
        ListNode* slow = h;
        ListNode* fast = h;
        while (fast != NULL && fast->next != NULL) 
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
c++
public ListNode middlenode() 
    {
        ListNode slow = h, fast = h;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
java


致读者: 小时百科一直以来坚持所有内容免费,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 10 元,我们一个星期内就能脱离亏损, 并保证在接下来的一整年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利