leetcode 160. Intersection of Two Linked Lists python

题目

Write a program to find the node at which the intersection of two singly linked lists begins.
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：brutal force

**首先理解题意指的是node所在的物理位置相同才代表是同一个节点，而不是单纯的节点value相同，看Example1就可以明白了。**采用双层循环的方法，TLE了

class Solution(object):def getIntersectionNode(self, headA, headB):""":type head1, head1: ListNode:rtype: ListNode"""tmp2 = headBwhile tmp2:tmp1 = headAwhile tmp1:if tmp1 == tmp2:return tmp1tmp1 = tmp1.nexttmp2 = tmp2.nextreturn None

时间复杂度：O(mn)
空间复杂度：O(1)

解法2：使用栈

利用intersection node之后的所有node都相同的特性，利用栈从后向前寻找交叉节点

class Solution(object):def getIntersectionNode(self, headA, headB):""":type head1, head1: ListNode:rtype: ListNode"""stackA = []stackB = []while headA:stackA.append(headA)headA = headA.nextwhile headB:stackB.append(headB)headB = headB.nextans = Nonewhile stackA and stackB:a = stackA.pop()b = stackB.pop()if a!=b:return anselse:ans = areturn ans

时间复杂度：O(m+n)
空间复杂度：O(n)

解法3：双指针法

分别从两个链表的头开始遍历，用p1代表第一条指针，p2代表第二条指针，当p1结束时，用p1去遍历第二条指针，p2结束时，用p2去遍历第一条指针，直到两个指针指向同一个node，这个node就是intersection node，其中用了一点技巧，举一个例子尝试变不难理解

class Solution(object):def getIntersectionNode(self, headA, headB):""":type head1, head1: ListNode:rtype: ListNode"""if headA==None or headB==None:return Nonep1 = headAp2 = headBwhile p1 != p2:p1 = headB if p1==None else p1.nextp2 = headA if p2==None else p2.nextreturn p1

c++版本

class Solution {
    
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if(!headA || !headB) return NULL;ListNode* p1 = headA;ListNode* p2 = headB;while(p1 != p2){
    p1 = p1 ? p1->next : headB;p2 = p2 ? p2->next : headA;}return p1;}
};

时间复杂度：O(m+n)
空间复杂度：O(1)

解法4：利用hashmap的思想

将一个链表的所有node放入一个字典或者是list中，遍历第二条链表寻找相同node

class Solution(object):def getIntersectionNode(self, headA, headB):""":type head1, head1: ListNode:rtype: ListNode"""memo = []while headA:memo.append(headA)headA = headA.nextwhile headB:if headB in memo:return headBheadB = headB.next

时间复杂度：O(m+n)
空间复杂度：O(n)