• LeetCode 142. 环形链表 II(Linker List Cycle II)


    题目描述

    给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

    说明:不允许修改给定的链表。

    进阶:
    你是否可以不用额外空间解决此题?

    解题思路

    分为三步:

    • 首先判断是否存在环,利用快慢指针法,从头节点开始快指针每次走两步,慢指针每次走一步,如果存在环则两指针必定会相遇,如果没有再次相遇则不存在环
    • 然后找到环中节点的个数,此时快指针已经处在环内,所以让其每次向前走一步,记录再次和慢指针相遇时走的步数即为环中节点个数
    • 找环入口节点时还是利用快慢指针,从头节点开始先让快指针走环中节点个数的步数,然后快慢指针同时向前移动,这样相遇时快指针恰好比满指针多走了一个环的长度,即指向了环入口节点

    代码

     1 /**
     2  * Definition for singly-linked list.
     3  * struct ListNode {
     4  *     int val;
     5  *     ListNode *next;
     6  *     ListNode(int x) : val(x), next(NULL) {}
     7  * };
     8  */
     9 class Solution {
    10 public:
    11     ListNode *detectCycle(ListNode *head) {
    12         if(head == NULL) return NULL;
    13         ListNode *fast = head, *slow = head;
    14         int len = 0;
    15         while(fast->next && fast->next->next){
    16             fast = fast->next->next;
    17             slow = slow->next;
    18             if(fast == slow){
    19                 len = 1;
    20                 break;
    21             }
    22         }
    23         if(len == 0) return NULL;
    24         while(fast->next != slow){
    25             fast = fast->next;
    26             len++;
    27         }
    28         fast = head;
    29         slow = head;
    30         while(len-- > 0)
    31             fast = fast->next;
    32         while(fast != slow){
    33             fast = fast->next;
    34             slow = slow->next;
    35         }
    36         return fast;
    37     }
    38 };
  • 相关阅读:
    vs错误集合及解决方案
    使用内存映射文件进行EXE、DLL通信(非MFC)
    visual studio使用小技巧(以vs2012为例)
    GetModuleHandle(NULL)获取当前DLL模块基址?
    格式化输出中的%s和%S的陷阱
    关于字符编码
    远程附加调试服务的方法
    结构体内包含位段,其数据内存分布
    微信个人公众号开发-java
    Docker-常用基建的安装与部署
  • 原文地址:https://www.cnblogs.com/wmx24/p/9468025.html
一二三 - 开发者的网上家园