Find intersection of two Linked Lists - O(A + B) Time Complexity and O(1) Space Complexity
Problem:
Two linked lists list1 and list2 are joined a particular node, called the point of intersection of the linked lists. Find the point of intersection, i.e. the first node after which both lists have same nodes. Desired order is O(A + B) Time Complexity and O(1) Space Complexity
Solution:
1: Find length of list1 – use a tmp1 node starting from head of list1 and move till last node.
2: Find length of list2 - use a tmp2 node starting from head of list2 and move till last node.
3: If tmp1 and tmp2 are different, it means that linked lists are non-intersecting. Return null.Example: list1: 1-2-3-4 , list2: 5-6-7-8, last nodes are separate.
4: Else set variables diff, tmp1 and tmp2 as:
tmp1 (a list node) to head node of larger list.
tmp2 (a list node) to head node of smaller list.
diff (an integer) to difference of lengths of larger to smaller lists i.e. absolute difference of the lengths.
5: Move forward tmp1 by diff number of nodes.
6: Now lists starting from tmp1 and tmp2 have same number of nodes and intersect at a particular node. Therefore, both tmp1 and tmp2 are equidistant from the intersection node.
7: Starting from tmp1 and tmp2 simultaneously, move node by node till a common node is reached. This node is the intersection of the 2 lists.
Code: http://www.ideserve.co.in/learn/find-intersection-of-two-linked-lists-constant-space
Website: http://www.ideserve.co.in
Facebook: https://www.facebook.com/IDeserve.co.in
Видео Find intersection of two Linked Lists - O(A + B) Time Complexity and O(1) Space Complexity канала IDeserve
Two linked lists list1 and list2 are joined a particular node, called the point of intersection of the linked lists. Find the point of intersection, i.e. the first node after which both lists have same nodes. Desired order is O(A + B) Time Complexity and O(1) Space Complexity
Solution:
1: Find length of list1 – use a tmp1 node starting from head of list1 and move till last node.
2: Find length of list2 - use a tmp2 node starting from head of list2 and move till last node.
3: If tmp1 and tmp2 are different, it means that linked lists are non-intersecting. Return null.Example: list1: 1-2-3-4 , list2: 5-6-7-8, last nodes are separate.
4: Else set variables diff, tmp1 and tmp2 as:
tmp1 (a list node) to head node of larger list.
tmp2 (a list node) to head node of smaller list.
diff (an integer) to difference of lengths of larger to smaller lists i.e. absolute difference of the lengths.
5: Move forward tmp1 by diff number of nodes.
6: Now lists starting from tmp1 and tmp2 have same number of nodes and intersect at a particular node. Therefore, both tmp1 and tmp2 are equidistant from the intersection node.
7: Starting from tmp1 and tmp2 simultaneously, move node by node till a common node is reached. This node is the intersection of the 2 lists.
Code: http://www.ideserve.co.in/learn/find-intersection-of-two-linked-lists-constant-space
Website: http://www.ideserve.co.in
Facebook: https://www.facebook.com/IDeserve.co.in
Видео Find intersection of two Linked Lists - O(A + B) Time Complexity and O(1) Space Complexity канала IDeserve
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
Programming Interview Question: How to print all diagonal's sums for a given binary tree?Level Order TraversalReverse a Linked List - IterativeProgramming Interview Question: Searching a 2D Sorted MatrixImplement a fair coin given an unfair coinBuying and selling stocksBinary SearchMinimum length subarray of an unsorted array sorting which results in complete sorted arrayFind an element in a sorted rotated array without finding pivot (minimum element)Maximum size square sub-matrix with all 1sBuilding Bridges Dynamic ProgrammingLeaders in an arrayCreate a balanced Binary Search Tree (BST) from a sorted arrayNext greater element in an arraySpiral level order traversal of a binary treeProgramming Interview Question: Recover Binary Search TreeDetect a loop in a linked listProgramming Interview Question: Find intersection of two Linked ListsFind an element in a sorted rotated arrayDemo of IDeserve web platform www.ideserve.co.in