Quoestion:Find the point of intersection of two singly linked lists begins.
Algorithm:
1.Calculate the size of both linked lists as L1,L2
2.Find the absolute difference of L1,L2 as d = L1-L2
3.Move d nodes in longer linked list
4.Then move by one step in both Linked Lists and Check if p==q if they are eaqual return p
Python Code:
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
l1size,l2size = 0,0
node = headA
while node:
l1size+=1
node = node.next
node = headB
while node:
node = node.next
l2size+=1
d = abs(l1size-l2size)
# print(d,l1size,l2size)
if l1size>l2size:
for i in range(d):
headA = headA.next
# print(headA.val)
else:
for i in range(d):
headB = headB.next
while True:
if headA == headB:
return headA
if headA:
headA = headA.next
else:
break
if headB:
headB = headB.next
else:
break
# print(headA.val,headB.val)
return
Algorithm:
1.Calculate the size of both linked lists as L1,L2
2.Find the absolute difference of L1,L2 as d = L1-L2
3.Move d nodes in longer linked list
4.Then move by one step in both Linked Lists and Check if p==q if they are eaqual return p
Python Code:
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
l1size,l2size = 0,0
node = headA
while node:
l1size+=1
node = node.next
node = headB
while node:
node = node.next
l2size+=1
d = abs(l1size-l2size)
# print(d,l1size,l2size)
if l1size>l2size:
for i in range(d):
headA = headA.next
# print(headA.val)
else:
for i in range(d):
headB = headB.next
while True:
if headA == headB:
return headA
if headA:
headA = headA.next
else:
break
if headB:
headB = headB.next
else:
break
# print(headA.val,headB.val)
return
0 Comments