Intersection of Two Linked Lists:
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
leetcode121,begin to intersect at node c1.
題意:找出給定的兩個鏈表,鏈表開始相交的交點。
思路:先分別遍歷兩個鏈表獲取兩個鏈表的長度,len1和len1,并定義兩個指針p和q,如果len1==len2則兩個指針分別同時指向鏈表的首節點;如果len1>len2或len1<len2,則指針p或q,指向第|len1-len2|個節點,然后在進行判斷。
代碼:
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int a_len = 0;int b_len = 0;ListNode p = headA;ListNode q = headB;while(p!=null){a_len++;p=p.next;}p = headB;while(p!=null){b_len++;p=p.next;}if(a_len==0||b_len==0){return null;}p = headA;q = headB;int sub_len = a_len - b_len;if(sub_len!=0){if(sub_len>0){while(sub_len>0){p = p.next;sub_len --;}}else{sub_len = -1*sub_len;while(sub_len>0){q= q.next;sub_len--;}}}while(p!=null&&q!=null){if(p==q){return p;}else{p = p.next;q = q.next;}}return null;}