LeetCode 题解(216) : Intersection of Two Linked Lists

本文主要是介绍LeetCode 题解(216) : 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.

题解：

先判断长度，再让长的先走完长的部分，然后比较。

C++版：

/*** 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* pA = headA, *pB = headB;int lA = 0, lB = 0;while(pA != NULL) {pA = pA->next;lA++;}while(pB != NULL) {pB = pB->next;lB++;}if(lA == 0 || lB == 0)return NULL;int i = 0;pA = headA;pB = headB;if(lA >= lB) {while(i < lA - lB) {pA = pA->next;i++;}} else {while(i < lB - lA) {pB = pB->next;i++;}}while(pA != NULL) {if(pA == pB)return pA;pA = pA->next;pB = pB->next;}return NULL;}
};

Java版：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pA = headA;ListNode pB = headB;int lA = 0;int lB = 0;while(pA != null) {pA = pA.next;lA++;}while(pB != null) {pB = pB.next;lB++;}int i = 0;pA = headA;pB = headB;if(lA >= lB) {while(i < lA - lB) {pA = pA.next;i++;}} else {while(i < lB - lA) {pB = pB.next;i++;}}while(pA != null) {if(pA == pB)return pA;pA = pA.next;pB = pB.next;}return null;}
}

Python版：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def getIntersectionNode(self, headA, headB):""":type head1, head1: ListNode:rtype: ListNode"""probA, probB = headA, headBlA, lB = 0, 0while probA != None:probA = probA.nextlA += 1while probB != None:probB = probB.nextlB += 1if lA == 0 or lB == 0:return NoneprobA, probB = headA, headBi = 0if lA >= lB:while i < lA - lB:probA = probA.nexti += 1else:while i < lB - lA:probB = probB.nexti += 1while probA != None:if probA == probB:return probAprobA = probA.nextprobB = probB.nextreturn None

这篇关于LeetCode 题解(216) : Intersection of Two Linked Lists的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---