双指针法运用

贡献者： 叶燊Leafshen

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]

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];
    }

　　 时间复杂度：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

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;
    }

　　 时间复杂度：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

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;
    }

public ListNode middlenode() 
    {
        ListNode slow = h, fast = h;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }