双指针法运用

贡献者：叶燊Leafshen

预备知识　双指针算法

本文处于草稿阶段。

例 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