劍指offer之求兩個連結清單的第一個公共節點

1 問題

輸入兩個連結清單，找出它們的第一個公共結點。

含有公共節點的兩個連結清單的結構類似于下圖中的連結清單：

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

              2 -> 4 ->5

可以看到兩個連結清單中有一個公共節點，其中4節點就是這兩個連結清單的公共節點  

2 分析

既然題目是求公共節點，說明一定存在這個節點，然後我們可以發現兩個連結清單的尾巴是一樣，都重合了是Y性結構，我們先把長的連結清單的頭移動到短的頭那裡，然後一個接着下一個比較就行

3 代碼實作

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node
{
  int value;
  struct Node *next;
} Node;
 
/*
 * 初始化結構體
 */
struct Node* init(struct Node *node, int value)
{
    node = (struct Node*)malloc(sizeof(Node));
    if (node != NULL)
    {
        node->value = value;
        //這個地方不要忘記設定為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;
}
 
/**
 * 找到第一個公共的節點
 */
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 運作結果

common node value is: 4      

5 總結

如果我們求連結清單的長度，一般是這樣的函數

/*
 * 擷取連結清單的長度
 */
int length(Node *head)
{
    if (head == NULL)
        return 0;
    Node *p = head;
    int length = 0;
    while (p != NULL)
    {
        length++;
        p = p->next;
    }
    return length;
}