劍指offer之找到鏈表里面包含環(huán)的入口節(jié)點(diǎn)

1 問(wèn)題

劍指offer之找到鏈表里面包含環(huán)的入口節(jié)點(diǎn)，比如

        //             node7<-node6 <-node5
        //              |              |
        //head->node1->node2->node3->node4

環(huán)的入口節(jié)點(diǎn)是node2


2 代碼實(shí)現(xiàn)

    #include <stdio.h>
    #include <stdlib.h>
     
    #define true 1
    #define false 0
     
    typedef struct node
    {
        int value;
        struct node *next;
    } Node;
     
     
    /**
     *得到環(huán)的第一個(gè)公共節(jié)點(diǎn)
     */
    Node *getCommonNode(Node *head)
    {
        if (head == NULL)
        {
            return NULL;
        }
        Node *first = NULL;
        Node *second = NULL;
        first = head;
        second = head;
        int isCircle = false;
        //判斷是否有環(huán)
        while (second != NULL && (second->next) != NULL && (second->next->next != NULL))
        {
            first = first->next;
            second = second->next->next;
            if (first == second)
            {
                isCircle = true;
                break;
            }
        }
        if (isCircle == false)
        {
            printf("the list do not circle\n");
            return NULL;   
        }
        //判斷環(huán)的大小,這個(gè)時(shí)候肯定是進(jìn)到環(huán)里面去了
        int len = 0;
        first = first->next;
        ++len;
        while (first != second)
        {
            len++;
            first = first->next;
        }
       
        //求出入口節(jié)點(diǎn)
        Node *start = head;
        Node *end = head;
        while (len-- > 0)
        {
            end = end->next;
        }
        while (start != end)
        {
            start = start->next;
            end = end->next;
        }
        return start;
    }
     
    int main()
    {
        Node *head = NULL;
        Node *node1 = NULL;
        Node *node2 = NULL;
        Node *node3 = NULL;
        Node *node4 = NULL;
        Node *node5 = NULL;
        Node *node6 = NULL;
        Node *node7 = NULL;
        head = (Node *)malloc(sizeof(Node));
        node1 = (Node *)malloc(sizeof(Node));
        node2 = (Node *)malloc(sizeof(Node));
        node3 = (Node *)malloc(sizeof(Node));
        node4 = (Node *)malloc(sizeof(Node));
        node5 = (Node *)malloc(sizeof(Node));
        node6 = (Node *)malloc(sizeof(Node));
        node7 = (Node *)malloc(sizeof(Node));
        if (head == NULL || node1 == NULL || node2 == NULL || node3 == NULL
            || node4 == NULL || node5 == NULL || node6 == NULL || node7 == NULL)
        {
            printf("malloc fail\n");
            return false;
        }
        //             node7<-node6 <-node5
        //              |              |
        //head->node1->node2->node3->node4
        head->value = 0;
        head->next = node1;
        node1->value = 1;
        node1->next = node2;
        node2->value = 2;
        node2->next = node3;
        node3->value = 3;
        node3->next = node4;
        node4->value = 4;
        node4->next = node5;
        node5->value = 5;
        node5->next = node6;
        node6->value = 6;
        node6->next = node7;
        node7->value = 7;
        node7->next = node2;
     
        Node *result = getCommonNode(head);
        if (result != NULL)
        {
            printf("the first common value is %d\n", result->value);
        }
        else
        {
            printf("list do not have circle\n");
        }
     
        return true;
    }


 
3 運(yùn)行結(jié)果

the first common value is 2



 




 


作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門(mén)到禿頭 或掃描下面二維碼
零基礎(chǔ)入門(mén)進(jìn)階人工智能(鏈接)