本文共 2468 字,大约阅读时间需要 8 分钟。
编写一个程序,找到两个单链表相交的起始节点。
如下面的两个链表**:**
在节点 c1 开始相交。
示例 1:
**输入:**intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
**输出:**Reference of the node with value = 8 **输入解释:**相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。示例 2:
**输入:**intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
**输出:**Reference of the node with value = 2 **输入解释:**相交节点的值为 2 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。示例 3:
**输入:**intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 **输出:**null **输入解释:**从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。 **解释:**这两个链表不相交,因此返回 null。注意:
null
.两个链表上的指针同时向前移动,当短的那个移动到尾部以后,从另一个头部继续移动;长的链表指针到达尾部以后同上,从短链表的头结点开始继续遍历,直到两个指针指向同一个节点。
/** * 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) { if(!headA||!headB){ return NULL; } ListNode *ta = headA, *tb = headB; while(ta!=tb){ if(!ta){ ta = headB; }else{ ta = ta->next; } if(!tb){ tb = headA; }else{ tb = tb->next; } } return ta; }};
先遍历两个链表分别求出其长度,然后相减得到差值,记为len
,那么长的那个链表就要先走len
步,接着和短链表的指针同时向前移动,直到两个指针指向同一个节点。
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if(!headA||!headB){ return NULL; } ListNode *ta = headA, *tb = headB; int ia=0,ib=0; while(ta){ ta = ta->next; ++ia; } while(tb){ tb = tb->next; ++ib; } int len = ia-ib; if(len>=0){ ta = headA; tb = headB; }else{ ta = headB; tb = headA; len = -len; } while(len--){ ta = ta->next; } while(ta!=tb){ ta = ta->next; tb = tb->next; } return ta; }};
转载地址:http://vlomf.baihongyu.com/