题目:相交链表.- 力扣(LeetCode)
第一思路:
先扫一遍两个链表,找到他两的长度m,n,将他俩移到相同的位置上,此时两个链表等长。然后开始等长的判断,如果走到相交的点。
时间复杂度 O(m + n), 空间复杂度O(1)
/*** 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;ListNode *p = headA, *q = headB;int m = 0, n = 0;while(p != NULL){p = p->next;m ++;}while(q != NULL){q = q->next;n ++;}p = headA, q = headB;if(m > n){while(m != n){p = p->next;m --;}}else {while(m != n){q = q->next;n --;}}while(p != q){p = p->next;q = q->next;}return p;}
};
第二思路:
如果B走完后就走A走过的路,如果走不到就更换另外一个链表走,这样,实际上是一个寻找子串的过程。这样,时间复杂度可以进一步优化到O(n)
举例:
1->2->3->4->5->6->3
3->4->5->6->1->2->3
思考:代码重与重新走headA而不是走headB的区别是什么?
如果重新走A,虽然仍能通过此题,但是实际上走了k * n + b == t * m + b的距离,成为了循环判断两个是否相同。而更换头以后,是在一个M + N中进行判断,最后在max(m,n)进行了判断,思路一则是m + n + b。
其中b为到相同节点的偏移量。
m,n为两个链表的长度。
k,t为两个链表的倍增值。
/*** 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;ListNode *p = headA, *q = headB;while (p != q) {p = p == NULL ? headB : p->next;q = q == NULL ? headA : q->next;}return p;}
};