单链表(面试算法题2)---单链表进阶1之快慢指针

单链表(面试算法题2)---单链表进阶1之快慢指针

单链表基础 *** 作可以参见我的另一篇博客：建议从基础到进阶

       单链表(面试算法题1)---学习链表的关键在于code

面试精要：对于部分问题会给出多种解决方案【在时间复杂度相同的情况下优化空间复杂度】

【在我们设计一个算法的时候，优先考虑时间复杂度最优。在时间复杂度相同的情况下再去优化空间复杂度】

今天我们探讨快慢指针在单链表中的四个经典问题(容易搞错)：

1）输入链表头节点，奇数长度返回中点，偶数长度返回上中点

2）输入链表头节点，奇数长度返回中点，偶数长度返回下中点

3）输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个

4）输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个

Les's go go go!

==》以上四个问题的模式是相同的，都是通过一个快指针fast和一个慢指针slow来找找中点。

        每一步fast眺两格，slow跳一格。当fast不满足跳两格的条件是，此时slow到达中点。

      【举例理解：小明和小明他爸同一时刻同从同一个起点出发，小明他爸每次都走的距离为小明的两倍。假设这段路程的总长度是length,则当小明他爸走到终点的时候，小明在什么位置。很明显小明走了length/2的路程，处在中点的位置】

        现在我们问题的模式搞懂了，要根据题目的不同条件来相应的初始位置。

      【为了简化问题，我们不妨先将返回头节点的情况单独拎出来，预先做处理】

问题1：奇数返回中点，偶数返回上中点。

 返回头节点的情况:链表为空 、只有一个节点的链表 、只有两个节点的链表

 处理完这个之后，我们就直到这个链表一定有大于等于三的节点。所以我们可以将slow和fast初始化为：

        

 附上代码：

//链表的基本在文章开头的博客链接中已经有了,不清楚的可以先阅读那篇内容
Node midOrUpMidNode(Node head){
    
    //先处理返回头节点的情况
    if(head == NULL || head->next == NULL || head->next->next == NULL){
        return head;
    }
    //其它情况
    Node slow = head->next;
    Node fast = head->next->next;

    while(fast->next != NULL && fast->next->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

问题2：奇数返回中点，偶数返回下中点。

我们来对比问题1的情况，奇数情况下是一样的，偶数情况下不同。问题2返回偶数的情况是问题1返回的下一个节点。所以问题解决了。显然，我们可以在之前做处理，也可以在之后在处理。

Node midOrDownMidNode(Node head){
    
    if(head==NULL || head->next==NULL){
        retrun head; 
    }
    
    Node slow = head->next;
    Node fast = head->next;
    
    while(fast->next==NULL && fast->next->next==NULL){
        fast=fast->next->next;
        slow=slow->next;
    }
    
    return slow

}

问题3：与问题1类似，但是需要多考虑一个条件就是返回为NULL的情况。

             当只有一个结点或者两个结点的时候，返回为NULL。

             其它情况只是将问题1的返回往前退了一步。

Node midOrUpMidPreNode(Node head){

    if(head==NULL || head->next==NULL || head->next->next==NULL){
        return NULL;
    }

    Node slow = head;
    Node fast = head->next->next;

    while(fast->next!=NULL && fast->next->next!=NULL){
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

 问题4：奇数长度返回中点前一个，偶数长度返回下中点前一个

               与问题2类似，不过要考虑返回NULL的情况。

               只有一个结点是返回为NULL

               其它情况返回都是问题2的返回的前一个结点。

                

Node midOrDownMidPreNode(Node head){
    if(head == NULL || head->next==NULL){
        return NULL;
    }
    if(head->next->next == NULL){
        return head;
    }
    Node slow = head;
    Node fast = head->next;
    while(fast->next != NULL && fast->next->next != NULL){
        slow = slow->next;
        fast = fast->next->next;    
    }
    return slow;

}