劍指offer之求兩個鏈表的第一個公共節(jié)點

1 問題

輸入兩個鏈表，找出它們的第一個公共結(jié)點。

含有公共節(jié)點的兩個鏈表的結(jié)構(gòu)類似于下圖中的鏈表：

1 -> 2 -> 3 -> 4 ->5

               2 -> 4 ->5

可以看到兩個鏈表中有一個公共節(jié)點，其中4節(jié)點就是這兩個鏈表的公共節(jié)點  
 
2 分析

既然題目是求公共節(jié)點，說明一定存在這個節(jié)點，然后我們可以發(fā)現(xiàn)兩個鏈表的尾巴是一樣，都重合了是Y性結(jié)構(gòu)，我們先把長的鏈表的頭移動到短的頭那里，然后一個接著下一個比較就行

3 代碼實現(xiàn)

    #include <stdio.h>
    #include <stdlib.h>
     
    typedef struct Node
    {
      int value;
      struct Node *next;
    } Node;
     
    /*
     * 初始化結(jié)構(gòu)體
     */
    struct Node* init(struct Node *node, int value)
    {
        node = (struct Node*)malloc(sizeof(Node));
        if (node != NULL)
        {
            node->value = value;
            //這個地方不要忘記設(shè)置為NULL
            node->next = NULL;
            return node;
        }
        return NULL;
    }
     
    /*
     * 獲取鏈表的長度
     */
    int length(Node *head)
    {
        if (head == NULL)
            return 0;
        Node *p = head;
        int length = 0;
        while (p != NULL)
        {
            length++;
            p = p->next;
        }
        return length;
    }
     
    /**
     * 找到第一個公共的節(jié)點
     */
    struct Node* get_common(Node *head1, Node *head2)
    {
        if (head1 == NULL || head2 == NULL)
        {
            return NULL;
        }
        int list1_length = length(head1);
        int list2_length = length(head2);
        Node *short_head = NULL;
        Node *long_head = NULL;
        int sub_len = 0;
        if (list1_length > list2_length)
        {
            short_head = head2;
            long_head = head1;
            sub_len = list1_length - list2_length;
        }
        else
        {
            short_head = head1;
            long_head = head2;
            sub_len = list2_length - list1_length;
        }
        //移動長鏈表，確保兩個鏈表一樣長
        while (sub_len > 0)
        {
            sub_len--;
            long_head = long_head->next;
        }
        while (short_head != NULL && long_head != NULL)
        {
            if (short_head->value == long_head->value)
            {
                return short_head;
            }
            short_head = short_head->next;
            long_head = long_head->next;
        }
        return NULL;
    }
     
     
    int main()
    {
        Node *n1 = NULL;
        Node *n2 = NULL;
        Node *n3 = NULL;
        Node *n4 = NULL;
        Node *n5 = NULL;
        Node *m1 = NULL;
        Node *m2 = NULL;
        Node *m3 = NULL;
     
        n1 = init(n1, 1);
        n2 = init(n2, 2);
        n3 = init(n3, 3);
        n4 = init(n4, 4);
        n5 = init(n5, 5);
     
        m1 = init(m1, 2);
        m2 = init(m2, 4);
        m3 = init(m3, 5);
     
        if (n1 && n2 && n3 && n4 && n5)
        {
            n1->next = n2;
            n2->next = n3;
            n3->next = n4;
            n4->next = n5;
        }
     
        if (m1 && m2 && m3)
        {
            m1->next = m2;
            m2->next = m3;
        }
     
        Node *node = get_common(n1, m2);
        if (node)
        {
            printf("common node value is: %d\n", node->value);
        }
        else
        {
            printf("two list do not common value\n");
        }
        if (n1) {free(n1); n1 = NULL;}
        if (n2) {free(n2); n2 = NULL;}
        if (n3) {free(n3); n3 = NULL;}
        if (n4) {free(n4); n4 = NULL;}
        if (n5) {free(n5); n5 = NULL;}
        if (m1) {free(m1); m1 = NULL;}
        if (m2) {free(m2); m1 = NULL;}
        if (m3) {free(m3); m1 = NULL;}
        return 1;
    }

4 運行結(jié)果

common node value is: 4

5 總結(jié)

如果我們求鏈表的長度，一般是這樣的函數(shù)

    /*
     * 獲取鏈表的長度
     */
    int length(Node *head)
    {
        if (head == NULL)
            return 0;
        Node *p = head;
        int length = 0;
        while (p != NULL)
        {
            length++;
            p = p->next;
        }
        return length;
    }

一定要記到骨髓里面去。



 


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