Write a PRogram to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3
Begin to intersect at node c1.
Notes: ● If the two linked lists have no intersection at all, return null. ● The linked lists must retain their original structure after the function returns. ● You may assume there are no cycles anywhere in the entire linked structure. ● Your code should preferably run in O(n) time and use only O(1) memory.
题目说明： 写一个程序找出两个单链表的交叉节点。 解题思路： 单链表A和单链表B，交叉点后的部分是一样的，也就是说长度是一样的，如上所示：c1 → c2 → c3。所以，将单链表A和单链表B相差的部分去掉，依次对应比较等长的部分即可。在计算两个链表的长度之后，比较两个链表的尾节点是否一样，如果不一样说明没有交叉节点，返回NULL。
Language:c
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *curA = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode *curB = (struct ListNode*)malloc(sizeof(struct ListNode)); curA = headA; curB = headB; int length_a = 1; int length_b = 1; int i = 0; if(curA == NULL || curB == NULL){ return NULL; } while(curA->next != NULL){ curA = curA->next; length_a++; } while(curB->next != NULL){ curB = curB->next; length_b++; } if(curA != curB){ return NULL; } curA = headA; curB = headB; if(length_a > length_b){ for(i; i < length_a-length_b; i++){ curA = curA->next; } i = 0; } else if(length_a < length_b){ for(i; i < length_b-length_a; i++){ curB = curB->next; } i = 0; } while(curA != curB){ curA = curA->next; curB = curB->next; } return curA;}Language:cpp
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *curA, *curB; curA = headA; curB = headB; if(curA == NULL || curB == NULL){ return NULL; } int length_a = getLength(curA); int length_b = getLength(curB); if(length_a > length_b){ for(int i=0; i < length_a-length_b; i++){ curA = curA->next; } } else if(length_a < length_b){ for(int i=0; i < length_b-length_a; i++){ curB = curB->next; } } while(curA != curB){ curA = curA->next; curB = curB->next; } return curA; }private: int getLength(ListNode *head){ int length = 1; while(head->next != NULL){ head = head->next; length++; } return length; }};新闻热点
疑难解答
