Leetcode 160.相交链表

Posted on |

160.相交链表

方法

  • 相交链表的相交结点之后是一样的，具有相同的结点
  • 链表A+B和链表B+A据哟相同的尾部，如

A=1,2,3
B=6,5,2,3

A+B=1,2,3,6,5,2,3
B+A=6,5,2,3,1,2,3

  • 同时实现A+B和B+A，一旦当前链表遍历结束，转到另一链表的head

  • 但是，你还需要留意，如果两个链表最终没有相交，在检查完A+B时应该停下来，设置一个flag jumpToNext保证指遍历A+B一遍

  • Leetcode Discussion:详细解释

方法1

下面两段代码的思路是一样的，但是第一段代码的效率更快

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        pA,pB=headA,headB
        while pA!=pB:
            pA=pA.next if pA else headB   # 这里只是确保pA，pB非空，但是不排除pA.next、pB.next是None
            pB=pB.next if pB else headA
        return pA                         # 要么返回相交结点，要么在遍历完A+B后没有返回相交结点，此时None==None，返回的pA是None

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        pA,pB,jumpToNext=headA,headB,True
        while pA and pB:
            if pA==pB:
                return pA
            pA,pB=pA.next,pB.next
            if not pA and jumpToNext:
                pA=headB
                jumpToNext=False
            if not pB:
                pB=headA
        return None

方法2

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
32
33
34
35
36
37
38
39
40
41
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        p = headA
        q = headB
        headA_len = 0
        while(p):
            headA_len +=1
            p = p.next
        headB_len = 0
        while(q):
            headB_len +=1
            q = q.next
        p = headA
        q = headB
        if headA_len<headB_len:
            for i in range(headB_len-headA_len):
                q = q.next
            for i in range(headA_len):
                if p==q:
                    return p
                p = p.next
                q = q.next
        else:
            for i in range(headA_len-headB_len):
                p = p.next
            for i in range(headB_len):
                if p == q:
                    return p
                p = p.next
                q = q.next
        return None
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
32
33
34
35
36
37
38
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def length(self,head):
        count=0
        while head:
            count+=1
            head=head.next
        return count


    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        pA,pB=headA,headB
        lenA,lenB=self.length(headA),self.length(headB)
        if lenA<lenB:
            n=lenB-lenA

            while n>0:
                n-=1
                pB=pB.next
        else:
            n=lenA-lenB
            while n>0:
                n-=1
                pA=pA.next
        while pA and pB:
            if pA==pB:
                return pA
            pA,pB=pA.next,pB.next
        return None