链表常见(典型)题目(一)快慢指针

此处的快慢指的是每次移动的步数

比如定义一个slow和fast指针都指向第一个节点:

ListNode *slow  = head;
ListNode *fast  = head;

slow每次走一步,fast每次走两步:

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

此处代码最终的slow将指向链表的中间节点

如果链表的节点个数为奇数如:1 2 3 4 5,slow则为3

        如果为偶数:1 2 3 4 5 6,则slow为第二个中间节点即为5

在纸上画一下,很容易证明上面的取得中间节点的结论

 

来看一个典型的快慢指针问题

判断单链表是否有环

结合生活中的场景我们不难想到:你是否有见过在一个环形跑道上赛跑的人,被猛男甩开几圈的场景。快慢指针同理,由于快指针步数比慢指针多,倘若有环,快指针必定会追上慢指针

代码如下:

bool hasCycle(ListNode* head) {
    if (head == NULL) {
        return false;
    }
    ListNode* ptr = head;

    ListNode* ptr2 = head->next;
    while (ptr != ptr2) {
        if (ptr2 == NULL ||ptr2->next ==NULL) {//如果把ptr2->next==NULL
            //放在前边则会报错
         /*   原因是没有判断当前指针是否指向了一个有意义的位置。
                我们只需要增加令其有意义的判断条件即可,即指针是否为NULL:*/
            return false;
        }
        ptr = ptr->next;
        ptr2 = ptr2->next->next;
    }
    return true;
}

 

 

 

上一篇:浙大版《C语言程序设计(第4版)》题目集——习题11-8 单链表结点删除 (20 分)


下一篇:C语言中ctime()和loacaltime()使用中遇到的问题