{"id":"1729eeec-4ee6-4e5d-af97-5a2ef54e057d","name":"Intersection Node In Two Linkedlist Using Floyad Cycle Method","description":"1. Given the heads of two singly linked-lists headA and headB\r\n2. Return the node at which the two lists intersect. \r\n3. If the two linked lists have no intersection, return null.\r\n","inputFormat":"Input is managed for you.","outputFormat":"Output is managed for you.","constraints":"0 <= N <= 10^6","sampleCode":{"cpp":{"code":"#include <iostream>\r\nusing namespace std;\r\n\r\nclass ListNode\r\n{\r\npublic:\r\n int val = 0;\r\n ListNode *next = nullptr;\r\n\r\n ListNode(int val)\r\n {\r\n this->val = val;\r\n }\r\n};\r\n\r\n#include <iostream>\r\nusing namespace std;\r\n\r\nclass ListNode\r\n{\r\npublic:\r\n int val = 0;\r\n ListNode *next = nullptr;\r\n\r\n ListNode(int val)\r\n {\r\n this->val = val;\r\n }\r\n};\r\n\r\nint lengthOfLL(ListNode *node)\r\n{\r\n if (node == nullptr)\r\n return 0;\r\n\r\n int len = 0;\r\n while (node != nullptr)\r\n {\r\n node = node->next;\r\n len++;\r\n }\r\n\r\n return len;\r\n}\r\n\r\nListNode *IntersectionNodeInTwoLL(ListNode *headA, ListNode *headB)\r\n{\r\n if (headA == nullptr || headB == nullptr)\r\n return nullptr;\r\n\r\n int l1 = lengthOfLL(headA);\r\n int l2 = lengthOfLL(headB);\r\n\r\n ListNode *biggerList = l1 > l2 ? headA : headB;\r\n ListNode *smallerList = l1 > l2 ? headB : headA;\r\n\r\n int diff = max(l1, l2) - min(l1, l2);\r\n while (diff-- > 0)\r\n biggerList = biggerList->next;\r\n\r\n while (biggerList != smallerList)\r\n {\r\n biggerList = biggerList->next;\r\n smallerList = smallerList->next;\r\n }\r\n\r\n return biggerList;\r\n}\r\n// Input_code===================================================\r\n\r\nListNode *makeList(int n)\r\n{\r\n ListNode *dummy = new ListNode(-1);\r\n ListNode *prev = dummy;\r\n while (n-- > 0)\r\n {\r\n int val;\r\n cin >> val;\r\n prev->next = new ListNode(val);\r\n prev = prev->next;\r\n }\r\n return dummy->next;\r\n}\r\n\r\nint main()\r\n{\r\n int n,idx;\r\n cin >> n;\r\n ListNode *head1 = makeList(n);\r\n cin >> idx;\r\n \r\n int m;\r\n cin >> m;\r\n ListNode *head2 = makeList(m);\r\n\r\n if (idx >= 0)\r\n {\r\n ListNode *curr = head1;\r\n\r\n while (idx-- > 0)\r\n curr = curr->next;\r\n\r\n ListNode *prev = head2;\r\n while (prev->next != nullptr)\r\n prev = prev->next;\r\n\r\n prev->next = curr;\r\n }\r\n\r\n ListNode *ans = IntersectionNodeInTwoLL(head1, head2);\r\n cout << (ans != nullptr ? ans->val : -1) << endl;\r\n return 0;\r\n}\r\n\r\n// Input_code===================================================\r\n\r\nListNode *makeList(int n)\r\n{\r\n ListNode *dummy = new ListNode(-1);\r\n ListNode *prev = dummy;\r\n while (n-- > 0)\r\n {\r\n int val;\r\n cin >> val;\r\n prev->next = new ListNode(val);\r\n prev = prev->next;\r\n }\r\n return dummy->next;\r\n}\r\n\r\nint main()\r\n{\r\n int n;\r\n cin >> n;\r\n ListNode *head1 = makeList(n);\r\n int m;\r\n cin >> m;\r\n ListNode *head2 = makeList(m);\r\n\r\n int idx;\r\n cin >> idx;\r\n if (idx >= 0)\r\n {\r\n ListNode *curr = head1;\r\n\r\n while (idx-- > 0)\r\n curr = curr->next;\r\n\r\n ListNode *prev = head2;\r\n while (prev->next != nullptr)\r\n prev = prev->next;\r\n\r\n prev->next = curr;\r\n }\r\n\r\n ListNode *ans = IntersectionNodeInTwoLL(head1, head2);\r\n cout << (ans != nullptr ? ans->val : -1) << endl;\r\n return 0;\r\n}\r\n"},"java":{"code":"import java.util.*;\r\n\r\nclass Main {\r\n public static Scanner scn = new Scanner(System.in);\r\n\r\n public static class ListNode {\r\n int val = 0;\r\n ListNode next = null;\r\n\r\n ListNode(int val) {\r\n this.val = val;\r\n }\r\n }\r\n\r\n public static ListNode IntersectionNodeInTwoLL(ListNode headA, ListNode headB) {\r\n return null;\r\n }\r\n\r\n // Input_code===================================================\r\n\r\n public static ListNode makeList(int n) {\r\n ListNode dummy = new ListNode(-1);\r\n ListNode prev = dummy;\r\n while (n-- > 0) {\r\n prev.next = new ListNode(scn.nextInt());\r\n prev = prev.next;\r\n }\r\n\r\n return dummy.next;\r\n }\r\n\r\n public static void main(String[] args) {\r\n ListNode head1 = makeList(scn.nextInt());\r\n\r\n int idx = scn.nextInt();\r\n\r\n ListNode head2 = makeList(scn.nextInt());\r\n\r\n if (idx >= 0) {\r\n ListNode curr = head1;\r\n while (idx-- > 0)\r\n curr = curr.next;\r\n\r\n ListNode prev = head2;\r\n while (prev.next != null)\r\n prev = prev.next;\r\n\r\n prev.next = curr;\r\n }\r\n\r\n ListNode ans = IntersectionNodeInTwoLL(head1, head2);\r\n System.out.println(ans != null ? ans.val : -1);\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"4\r\n14 12 8 7 \r\n2\r\n4\r\n7 2 6 5 \r\n","sampleOutput":"8\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"1e4c8949-5890-4d15-be5b-6601c7e2029a","name":"Linked List For Intermediate","slug":"linked-list-for-intermediate-637","type":0},{"id":"26e53bb9-2397-4fa0-b593-3849419e3c27","name":"Intersection Node In Two Linkedlist Using Floyad Cycle Method","slug":"intersection-node-in-two-linkedlist-using-floyad-cycle-method","type":1}],"next":{"id":"7a4cf78a-0f39-4a6b-95a1-4de1031b59d7","name":"Intersection Node In Linkedlist Using Difference Method MCQ","type":0,"slug":"intersection-node-in-linkedlist-using-difference-method-mcq"},"prev":{"id":"2cf9795e-30c0-43df-aced-36af1782140a","name":"Intersection node in two linked lists using difference method.","type":3,"slug":"intersection-node-in-two-linked-lists-using-difference-method"}}}1. Given the heads of two singly linked-lists headA and headB 2. Return the node at which the two lists intersect. 3. If the two linked lists have no intersection, return null.
{"id":"1729eeec-4ee6-4e5d-af97-5a2ef54e057d","name":"Intersection Node In Two Linkedlist Using Floyad Cycle Method","description":"1. Given the heads of two singly linked-lists headA and headB\r\n2. Return the node at which the two lists intersect. \r\n3. If the two linked lists have no intersection, return null.\r\n","inputFormat":"Input is managed for you.","outputFormat":"Output is managed for you.","constraints":"0 <= N <= 10^6","sampleCode":{"cpp":{"code":"#include <iostream>\r\nusing namespace std;\r\n\r\nclass ListNode\r\n{\r\npublic:\r\n int val = 0;\r\n ListNode *next = nullptr;\r\n\r\n ListNode(int val)\r\n {\r\n this->val = val;\r\n }\r\n};\r\n\r\n#include <iostream>\r\nusing namespace std;\r\n\r\nclass ListNode\r\n{\r\npublic:\r\n int val = 0;\r\n ListNode *next = nullptr;\r\n\r\n ListNode(int val)\r\n {\r\n this->val = val;\r\n }\r\n};\r\n\r\nint lengthOfLL(ListNode *node)\r\n{\r\n if (node == nullptr)\r\n return 0;\r\n\r\n int len = 0;\r\n while (node != nullptr)\r\n {\r\n node = node->next;\r\n len++;\r\n }\r\n\r\n return len;\r\n}\r\n\r\nListNode *IntersectionNodeInTwoLL(ListNode *headA, ListNode *headB)\r\n{\r\n if (headA == nullptr || headB == nullptr)\r\n return nullptr;\r\n\r\n int l1 = lengthOfLL(headA);\r\n int l2 = lengthOfLL(headB);\r\n\r\n ListNode *biggerList = l1 > l2 ? headA : headB;\r\n ListNode *smallerList = l1 > l2 ? headB : headA;\r\n\r\n int diff = max(l1, l2) - min(l1, l2);\r\n while (diff-- > 0)\r\n biggerList = biggerList->next;\r\n\r\n while (biggerList != smallerList)\r\n {\r\n biggerList = biggerList->next;\r\n smallerList = smallerList->next;\r\n }\r\n\r\n return biggerList;\r\n}\r\n// Input_code===================================================\r\n\r\nListNode *makeList(int n)\r\n{\r\n ListNode *dummy = new ListNode(-1);\r\n ListNode *prev = dummy;\r\n while (n-- > 0)\r\n {\r\n int val;\r\n cin >> val;\r\n prev->next = new ListNode(val);\r\n prev = prev->next;\r\n }\r\n return dummy->next;\r\n}\r\n\r\nint main()\r\n{\r\n int n,idx;\r\n cin >> n;\r\n ListNode *head1 = makeList(n);\r\n cin >> idx;\r\n \r\n int m;\r\n cin >> m;\r\n ListNode *head2 = makeList(m);\r\n\r\n if (idx >= 0)\r\n {\r\n ListNode *curr = head1;\r\n\r\n while (idx-- > 0)\r\n curr = curr->next;\r\n\r\n ListNode *prev = head2;\r\n while (prev->next != nullptr)\r\n prev = prev->next;\r\n\r\n prev->next = curr;\r\n }\r\n\r\n ListNode *ans = IntersectionNodeInTwoLL(head1, head2);\r\n cout << (ans != nullptr ? ans->val : -1) << endl;\r\n return 0;\r\n}\r\n\r\n// Input_code===================================================\r\n\r\nListNode *makeList(int n)\r\n{\r\n ListNode *dummy = new ListNode(-1);\r\n ListNode *prev = dummy;\r\n while (n-- > 0)\r\n {\r\n int val;\r\n cin >> val;\r\n prev->next = new ListNode(val);\r\n prev = prev->next;\r\n }\r\n return dummy->next;\r\n}\r\n\r\nint main()\r\n{\r\n int n;\r\n cin >> n;\r\n ListNode *head1 = makeList(n);\r\n int m;\r\n cin >> m;\r\n ListNode *head2 = makeList(m);\r\n\r\n int idx;\r\n cin >> idx;\r\n if (idx >= 0)\r\n {\r\n ListNode *curr = head1;\r\n\r\n while (idx-- > 0)\r\n curr = curr->next;\r\n\r\n ListNode *prev = head2;\r\n while (prev->next != nullptr)\r\n prev = prev->next;\r\n\r\n prev->next = curr;\r\n }\r\n\r\n ListNode *ans = IntersectionNodeInTwoLL(head1, head2);\r\n cout << (ans != nullptr ? ans->val : -1) << endl;\r\n return 0;\r\n}\r\n"},"java":{"code":"import java.util.*;\r\n\r\nclass Main {\r\n public static Scanner scn = new Scanner(System.in);\r\n\r\n public static class ListNode {\r\n int val = 0;\r\n ListNode next = null;\r\n\r\n ListNode(int val) {\r\n this.val = val;\r\n }\r\n }\r\n\r\n public static ListNode IntersectionNodeInTwoLL(ListNode headA, ListNode headB) {\r\n return null;\r\n }\r\n\r\n // Input_code===================================================\r\n\r\n public static ListNode makeList(int n) {\r\n ListNode dummy = new ListNode(-1);\r\n ListNode prev = dummy;\r\n while (n-- > 0) {\r\n prev.next = new ListNode(scn.nextInt());\r\n prev = prev.next;\r\n }\r\n\r\n return dummy.next;\r\n }\r\n\r\n public static void main(String[] args) {\r\n ListNode head1 = makeList(scn.nextInt());\r\n\r\n int idx = scn.nextInt();\r\n\r\n ListNode head2 = makeList(scn.nextInt());\r\n\r\n if (idx >= 0) {\r\n ListNode curr = head1;\r\n while (idx-- > 0)\r\n curr = curr.next;\r\n\r\n ListNode prev = head2;\r\n while (prev.next != null)\r\n prev = prev.next;\r\n\r\n prev.next = curr;\r\n }\r\n\r\n ListNode ans = IntersectionNodeInTwoLL(head1, head2);\r\n System.out.println(ans != null ? ans.val : -1);\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"4\r\n14 12 8 7 \r\n2\r\n4\r\n7 2 6 5 \r\n","sampleOutput":"8\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"1e4c8949-5890-4d15-be5b-6601c7e2029a","name":"Linked List For Intermediate","slug":"linked-list-for-intermediate-637","type":0},{"id":"26e53bb9-2397-4fa0-b593-3849419e3c27","name":"Intersection Node In Two Linkedlist Using Floyad Cycle Method","slug":"intersection-node-in-two-linkedlist-using-floyad-cycle-method","type":1}],"next":{"id":"7a4cf78a-0f39-4a6b-95a1-4de1031b59d7","name":"Intersection Node In Linkedlist Using Difference Method MCQ","type":0,"slug":"intersection-node-in-linkedlist-using-difference-method-mcq"},"prev":{"id":"2cf9795e-30c0-43df-aced-36af1782140a","name":"Intersection node in two linked lists using difference method.","type":3,"slug":"intersection-node-in-two-linked-lists-using-difference-method"}}}
Editor
Discussions
Show Discussion
Related Resources
