面试题02.07链表相交
暴力循环
两层循环,分别循环两个链表
/** * 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 *dummy_a = new ListNode(0,NULL); ListNode *dummy_b = new ListNode(0,NULL); ListNode *temp, *tempA , *tempB; int flag = 0; dummy_a->next = headA; dummy_b->next = headB; tempA = dummy_a; tempB = dummy_b; if(headA == headB) return headA; while(tempA->next != NULL) { while(tempB->next != NULL) { if(tempA == tempB) { return tempA; } tempB = tempB->next; } tempB = dummy_b; tempA = tempA->next; } while(dummy_b) { if(tempA == dummy_b)return tempA; dummy_b = dummy_b->next; } while(dummy_a) { if(tempB == dummy_a)return tempB; dummy_a = dummy_a->next; } return 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) { int length_A = 0 , length_B = 0 ,diff=0 ; ListNode *cur_A = headA , *cur_B = headB; ListNode *dummy_a = new ListNode(0); ListNode *dummy_b = new ListNode(0); dummy_a->next = headA; dummy_b->next = headB; while(dummy_a->next != NULL) { length_A++; dummy_a = dummy_a->next; } while(dummy_b->next != NULL) { length_B++; dummy_b = dummy_b->next; } if(length_A >= length_B) { for(int i =0;i< length_A-length_B;i++) { cur_A = cur_A->next; } }else { for(int i =0;i< length_B-length_A;i++) { cur_B = cur_B->next; } } while(cur_A != cur_B) { cur_A = cur_A->next; cur_B = cur_B->next; } return cur_A; } };
二刷
/** * 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==NULL || headB==NULL)return NULL; int numA = 0 ,numB = 0 , diff =0; ListNode *cur_A = headA; ListNode *cur_B = headB; while(cur_A != NULL) { cur_A = cur_A->next; numA++ ; } while(cur_B != NULL) { cur_B = cur_B->next; numB++ ; } cur_A = headA; cur_B = headB; if(numA > numB) { diff = numA -numB; while(diff--) cur_A = cur_A->next; }else if(numA < numB) { diff = numB - numA; while(diff--) cur_B = cur_B->next; } // cout<<cur_A->val<<' '<<cur_B->val; while(cur_A != NULL) { if(cur_A == cur_B) return cur_A; cur_A = cur_A->next; cur_B = cur_B->next; } return NULL; } };