交叉链表

无可奈何花落去 似曾相识燕归来

前言

两个链表list1和list2如果中间有一个交汇点。怎样在线性时间内求出这个交汇点？

思路

分别求出两个链表的长度
把长链做偏移和短链一样长
同时移动两个链表的首指针，判断节点是否相等
相等则找到交叉点

代码实现

    // 定义节点    typedef struct Node {        int data;        struct Node *next;    } Node;        /// 计算链表的长度    int getListLength(Node *list) {        int length = 1;        while (list->next != NULL) {            length++;            list = list->next;        }        return length;    }        // 长链表做偏移    Node* relocateNode (Node *list, int offset) {        Node *node1 = list;        for (NSInteger i = 0; i < offset; i++) {            node1 = node1->next;        }        return node1;    }        int findCommonNode (Node *list1, Node *list2) {        // 计算两个链表的长度        int list1Length = getListLength(list1);        int list2Length = getListLength(list2);                // 计算两个链表的长度差值        int offset = abs(list1Length-list2Length);                // 记录长链短链        Node *longList = list1;        Node *shortList = list2;        if (list1Length < list2Length) {            longList = list2;            shortList = list1;        }        // 长链做偏移 ，偏移后和短链一样长        longList = relocateNode(longList, offset);                // 同时移动两个链表的首指针        while (shortList != NULL) {            if (longList->data == shortList->data) {                // 如果节点值相等 找到交叉点                return longList->data;            }            longList = longList->next;            shortList = shortList->next;        }        return 0;    }        int main(int argc, const char * argv[]) {        @autoreleasepool {                        Node *node1 = malloc(sizeof(Node));            node1->data = 1;            Node *node2 = malloc(sizeof(Node));            node2->data = 2;            Node *node3 = malloc(sizeof(Node));            node3->data = 3;            Node *node4 = malloc(sizeof(Node));            node4->data = 4;            Node *node5 = malloc(sizeof(Node));            node5->data = 5;            Node *node6 = malloc(sizeof(Node));            node6->data = 6;                        Node *node7 = malloc(sizeof(Node));            node7->data = 7;                        node1->next = node2;            node2->next = node3;            node3->next = node4;            node4->next = node5;            node5->next = node6;            node6->next = NULL;                        node7->next = node4;                                    Node *list1 = node1; // 1 2 3 4 5 6            Node *list2 = node7; // 7 4 5 6                                    int commonValue = findCommonNode(list1, list2);            NSLog(@"commonValue: %d\b", commonValue);// 4        }        return 0;    }

测试结果

源码地址

链接描述