[LeetCode]160.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 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.

分析:找出两个链表的交点[交点之后不会再有分叉]:

  1. 暴力法 两层循环:确定链表A,遍历链表B,A中当前元素与B中所有元素相比,相等,返回;B遍历完成后,A指向下一个元素,B重新指向B开头元素。时间复杂度为O(N * N)

  2. 计算长度法 获取两个链表的各自长度;长链表先移动一部分,确保移动后A、B链表长度相同;之后再遍历两个链表;如果相等,则返回相应结点;否则返回null

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int Alen = getListLength(headA);
int Blen = getListLength(headB);

int sub = Alen - Blen;
ListNode* list1 = headA, *list2 = headB;

for(int i=0;i<abs(sub);i++){
if(sub > 0) list1 = list1->next;
else list2 = list2->next;
}

while(list1 && list2){
if(list1 == list2)
return list1;
list1 = list1->next;
list2 = list2->next;
}
return NULL;
}
int getListLength(ListNode* head){
int count = 0;
while(head){
count++;
head = head->next;
}
return count;
}
};
您的支持就是我更新的最大动力!谢谢!