{"id":"18add11b-4c3e-4198-b2b4-9b502c3ee0c4","name":"Intersection Point Of Linked Lists","description":"1. You are given a partially written LinkedList class.\r\n2. You are required to complete the body of findIntersection function. The function is passed two linked lists which start separately but merge at a node and become common thereafter. The function is expected to find the point where two linked lists merge. You are not allowed to use arrays to solve the problem.\r\n3. Input and Output is managed for you. \r\n\r\n<img src=\"http://pepcoding.com/resources/ojquestionresource/images/intersection-of-linked-list.jpeg\" alt=\"intersection-of-linked-list\">","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1. Time complexity -&gt; O(n)\r\n2. Space complexity -&gt; constant","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <bits/stdc++.h>\n\nusing namespace std;\n\n class Node\n {\n public:\n int data = 0;\n Node *next = nullptr;\n\n Node(int data)\n {\n this->data = data;\n }\n };\n\n\n\nclass linkedlist\n{\n \npublic:\n\n Node *head = nullptr;\n Node *tail = nullptr;\n int size = 0;\n\n //basic->============================================\n\n int size_()\n {\n return this->size;\n }\n\n bool isEmpty()\n {\n return this->size == 0;\n }\n\n string toString()\n {\n Node *curr = this->head;\n string sb = \"\";\n\n while (curr != nullptr)\n {\n sb += to_string(curr->data);\n if (curr->next != nullptr)\n sb += \" \";\n curr = curr->next;\n }\n return sb;\n }\n\n //add->===============================================\nprivate:\n void addFirstNode(Node *node)\n {\n if (this->head == nullptr)\n {\n this->head = node;\n this->tail = node;\n }\n else\n {\n node->next = this->head;\n this->head = node;\n }\n\n this->size++;\n }\n\npublic:\n void addFirst(int val)\n {\n Node *node = new Node(val);\n addFirstNode(node);\n }\n\npublic:\n void addLastNode(Node *node)\n {\n if (this->head == nullptr)\n {\n this->head = node;\n this->tail = node;\n }\n else\n {\n this->tail->next = node;\n this->tail = node;\n }\n\n this->size++;\n }\n\n void addLast(int val)\n {\n Node *node = new Node(val);\n addLastNode(node);\n }\n\n void addNodeAt(Node *node, int idx)\n {\n if (idx == 0)\n addFirstNode(node);\n else if (idx == this->size)\n addLastNode(node);\n else\n {\n Node *prev = getNodeAt(idx - 1);\n Node *curr = prev->next;\n\n prev->next = node;\n curr->next = node;\n\n this->size++;\n }\n }\n\n void addAt(int data, int idx)\n {\n if (idx < 0 || idx > this->size)\n {\n throw(\"invalidLocation: \" + to_string(idx));\n }\n\n Node *node = new Node(data);\n addNodeAt(node, idx);\n }\n\n //remove->============================================\n Node *removeFirstNode()\n {\n Node *node = this->head;\n if (this->size == 1)\n {\n this->head = nullptr;\n this->tail = nullptr;\n }\n else\n {\n this->head = this->head->next;\n node->next = nullptr;\n }\n\n this->size--;\n return node;\n }\n\n int removeFirst(int val)\n {\n if (this->size == 0)\n {\n throw(\"nullptrPointerException: -1\");\n }\n\n Node *node = removeFirstNode();\n int rv = node->data;\n delete node;\n return rv;\n }\n\n Node *removeLastNode()\n {\n Node *node = this->tail;\n if (this->size == 1)\n {\n this->head = nullptr;\n this->tail = nullptr;\n }\n else\n {\n Node *prev = getNodeAt(this->size - 2);\n this->tail = prev;\n prev->next = nullptr;\n }\n\n this->size--;\n return node;\n }\n\n int removeLast(int val)\n {\n if (this->size == 0)\n {\n throw(\"nullptrPointerException: -1\");\n }\n\n Node *node = new Node(val);\n int rv = node->data;\n delete node;\n return rv;\n }\n\n Node *removeNodeAt(int idx)\n {\n if (idx == 0)\n return removeFirstNode();\n else if (idx == this->size - 1)\n return removeLastNode();\n else\n {\n\n Node *prev = getNodeAt(idx - 1);\n Node *curr = prev->next;\n\n prev->next = curr->next;\n curr->next = nullptr;\n\n this->size--;\n return curr;\n }\n }\n\n int removeAt(int idx)\n {\n if (idx < 0 || idx >= this->size)\n {\n throw(\"invalidLocation: \" + idx);\n }\n\n Node *node = removeNodeAt(idx);\n int rv = node->data;\n delete node;\n return rv;\n }\n\n //get->================================================\n Node *getFirstNode()\n {\n return this->head;\n }\n\n int getFirst()\n {\n if (this->size == 0)\n {\n throw(\"nullptrPointerException: -1\");\n }\n\n Node *node = getFirstNode();\n return node->data;\n }\n\n Node *getLastNode()\n {\n return this->tail;\n }\n\n int getLast()\n {\n if (this->size == 0)\n {\n throw(\"nullptrPointerException\");\n }\n\n Node *node = getLastNode();\n return node->data;\n }\n\n Node *getNodeAt(int idx)\n {\n Node *curr = this->head;\n\n while (idx-- > 0)\n {\n curr = curr->next;\n }\n\n return curr;\n }\n\n int getAt(int idx)\n {\n if (idx < 0 || idx >= this->size)\n {\n throw(\"invalidLocation: \" + idx);\n }\n\n Node *node = getNodeAt(idx);\n return node->data;\n }\n};\n\n Node* getMid(Node* head, Node* tail){\n Node* slow = head, *fast = head;\n while(fast->next != tail && fast->next->next != tail){\n fast = fast->next->next;\n slow = slow->next;\n }\n \n return slow;\n }\n\n\n //merge two sorted linkedlist\n linkedlist mergeTwoSortedLists(linkedlist l1, linkedlist l2) {\n linkedlist ans;\n Node* one = l1.head;\n Node* two = l2.head;\n \n while(one != nullptr && two != nullptr){\n if(one->data < two->data){\n ans.addLast(one->data);\n one = one->next;\n }else{\n ans.addLast(two->data);\n two = two->next;\n }\n }\n while(one!=nullptr){\n ans.addLast(one->data);\n one = one->next;\n }\n while(two !=nullptr){\n ans.addLast(two->data);\n two = two->next;\n }\n \n return ans;\n }\n \n linkedlist mergeSort(Node* head,Node* tail ){\n if(head == tail){\n linkedlist base;\n base.addLast(head->data);\n return base;\n }\n \n Node* mid = getMid(head,tail);\n linkedlist fsh = mergeSort(head, mid);\n linkedlist ssh = mergeSort(mid->next, tail);\n \n return mergeTwoSortedLists(fsh,ssh);\n }\n \n int addTwoLists(Node* on, Node* tn, int pio, int pit, linkedlist & res){\n if(on == nullptr && tn == nullptr){\n return 0;\n }\n\n int carry = 0;\n int data = 0;\n if(pio > pit){\n carry = addTwoLists(on->next, tn, pio - 1, pit, res);\n data = carry + on->data;\n } else if(pio < pit){\n carry = addTwoLists(on, tn->next, pio, pit - 1, res);\n data = carry + tn->data;\n } else {\n carry = addTwoLists(on->next, tn->next, pio - 1, pit - 1, res);\n data = carry + on->data + tn->data;\n }\n\n carry = data / 10;\n data = data % 10;\n\n res.addFirst(data);\n return carry;\n }\n\n linkedlist addTwoLists(linkedlist one, linkedlist two) {\n linkedlist res ;\n\n int carry = addTwoLists(one.head, two.head, one.size, two.size, res);\n if(carry > 0){\n res.addFirst(carry);\n }\n\n return res;\n }\n \nlinkedlist makeList() {\n linkedlist l;\n int n1;\n cin >> n1;\n\n for (int i = 0; i < n1; i++) {\n int val;\n cin >> val;\n l.addLast(val);\n }\n return l;\n}\n\n\nint findIntersection(linkedlist one, linkedlist two)\n{\n // write your code here \n}\n\n\nint main()\n{\n\n linkedlist l1= makeList();\n linkedlist l2= makeList();\n int li;\n cin>>li;\n int di;\n cin>>di;\n if (li == 1) {\n Node * n = l1.getNodeAt(di);\n\n if (l2.size > 0) {\n l2.tail->next = n;\n } else {\n l2.head = n;\n }\n\n l2.tail = l1.tail;\n l2.size += l1.size - di;\n } else {\n Node *n = l2.getNodeAt(di);\n\n if (l1.size > 0) {\n l1.tail->next = n;\n } else {\n l1.head = n;\n }\n\n l1.tail = l2.tail;\n l1.size += l2.size - di;\n \n }\n \n \n int s =findIntersection(l1,l2);\n cout <<s<< endl;\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static class Node {\r\n int data;\r\n Node next;\r\n }\r\n\r\n public static class LinkedList {\r\n Node head;\r\n Node tail;\r\n int size;\r\n\r\n void addLast(int val) {\r\n Node temp = new Node();\r\n temp.data = val;\r\n temp.next = null;\r\n\r\n if (size == 0) {\r\n head = tail = temp;\r\n } else {\r\n tail.next = temp;\r\n tail = temp;\r\n }\r\n\r\n size++;\r\n }\r\n\r\n public int size() {\r\n return size;\r\n }\r\n\r\n public void display() {\r\n for (Node temp = head; temp != null; temp = temp.next) {\r\n System.out.print(temp.data + \" \");\r\n }\r\n System.out.println();\r\n }\r\n\r\n public void removeFirst() {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n } else if (size == 1) {\r\n head = tail = null;\r\n size = 0;\r\n } else {\r\n head = head.next;\r\n size--;\r\n }\r\n }\r\n\r\n public int getFirst() {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n return -1;\r\n } else {\r\n return head.data;\r\n }\r\n }\r\n\r\n public int getLast() {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n return -1;\r\n } else {\r\n return tail.data;\r\n }\r\n }\r\n\r\n public int getAt(int idx) {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n return -1;\r\n } else if (idx < 0 || idx >= size) {\r\n System.out.println(\"Invalid arguments\");\r\n return -1;\r\n } else {\r\n Node temp = head;\r\n for (int i = 0; i < idx; i++) {\r\n temp = temp.next;\r\n }\r\n return temp.data;\r\n }\r\n }\r\n\r\n public void addFirst(int val) {\r\n Node temp = new Node();\r\n temp.data = val;\r\n temp.next = head;\r\n head = temp;\r\n\r\n if (size == 0) {\r\n tail = temp;\r\n }\r\n\r\n size++;\r\n }\r\n\r\n public void addAt(int idx, int val) {\r\n if (idx < 0 || idx > size) {\r\n System.out.println(\"Invalid arguments\");\r\n } else if (idx == 0) {\r\n addFirst(val);\r\n } else if (idx == size) {\r\n addLast(val);\r\n } else {\r\n Node node = new Node();\r\n node.data = val;\r\n\r\n Node temp = head;\r\n for (int i = 0; i < idx - 1; i++) {\r\n temp = temp.next;\r\n }\r\n node.next = temp.next;\r\n\r\n temp.next = node;\r\n size++;\r\n }\r\n }\r\n\r\n public void removeLast() {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n } else if (size == 1) {\r\n head = tail = null;\r\n size = 0;\r\n } else {\r\n Node temp = head;\r\n for (int i = 0; i < size - 2; i++) {\r\n temp = temp.next;\r\n }\r\n\r\n tail = temp;\r\n tail.next = null;\r\n size--;\r\n }\r\n }\r\n\r\n public void removeAt(int idx) {\r\n if (idx < 0 || idx >= size) {\r\n System.out.println(\"Invalid arguments\");\r\n } else if (idx == 0) {\r\n removeFirst();\r\n } else if (idx == size - 1) {\r\n removeLast();\r\n } else {\r\n Node temp = head;\r\n for (int i = 0; i < idx - 1; i++) {\r\n temp = temp.next;\r\n }\r\n\r\n temp.next = temp.next.next;\r\n size--;\r\n }\r\n }\r\n\r\n private Node getNodeAt(int idx) {\r\n Node temp = head;\r\n for (int i = 0; i < idx; i++) {\r\n temp = temp.next;\r\n }\r\n return temp;\r\n }\r\n\r\n public void reverseDI() {\r\n int li = 0;\r\n int ri = size - 1;\r\n while (li < ri) {\r\n Node left = getNodeAt(li);\r\n Node right = getNodeAt(ri);\r\n\r\n int temp = left.data;\r\n left.data = right.data;\r\n right.data = temp;\r\n\r\n li++;\r\n ri--;\r\n }\r\n }\r\n\r\n public void reversePI() {\r\n if (size <= 1) {\r\n return;\r\n }\r\n\r\n Node prev = null;\r\n Node curr = head;\r\n while (curr != null) {\r\n Node next = curr.next;\r\n\r\n curr.next = prev;\r\n prev = curr;\r\n curr = next;\r\n }\r\n\r\n Node temp = head;\r\n head = tail;\r\n tail = temp;\r\n }\r\n\r\n public int kthFromLast(int k) {\r\n Node slow = head;\r\n Node fast = head;\r\n for (int i = 0; i < k; i++) {\r\n fast = fast.next;\r\n }\r\n\r\n while (fast != tail) {\r\n slow = slow.next;\r\n fast = fast.next;\r\n }\r\n\r\n return slow.data;\r\n }\r\n\r\n public int mid() {\r\n Node f = head;\r\n Node s = head;\r\n\r\n while (f.next != null && f.next.next != null) {\r\n f = f.next.next;\r\n s = s.next;\r\n }\r\n\r\n return s.data;\r\n }\r\n\r\n public static LinkedList mergeTwoSortedLists(LinkedList l1, LinkedList l2) {\r\n LinkedList ml = new LinkedList();\r\n\r\n Node one = l1.head;\r\n Node two = l2.head;\r\n while (one != null && two != null) {\r\n if (one.data < two.data) {\r\n ml.addLast(one.data);\r\n one = one.next;\r\n } else {\r\n ml.addLast(two.data);\r\n two = two.next;\r\n }\r\n }\r\n\r\n while (one != null) {\r\n ml.addLast(one.data);\r\n one = one.next;\r\n }\r\n\r\n while (two != null) {\r\n ml.addLast(two.data);\r\n two = two.next;\r\n }\r\n\r\n return ml;\r\n }\r\n\r\n public static Node midNode(Node head, Node tail) {\r\n Node f = head;\r\n Node s = head;\r\n\r\n while (f != tail && f.next != tail) {\r\n f = f.next.next;\r\n s = s.next;\r\n }\r\n\r\n return s;\r\n }\r\n\r\n public static LinkedList mergeSort(Node head, Node tail) {\r\n if (head == tail) {\r\n LinkedList br = new LinkedList();\r\n br.addLast(head.data);\r\n return br;\r\n }\r\n\r\n Node mid = midNode(head, tail);\r\n LinkedList fsh = mergeSort(head, mid);\r\n LinkedList ssh = mergeSort(mid.next, tail);\r\n LinkedList sl = mergeTwoSortedLists(fsh, ssh);\r\n return sl;\r\n }\r\n\r\n public void removeDuplicates() {\r\n LinkedList res = new LinkedList();\r\n\r\n while (this.size() > 0) {\r\n int val = this.getFirst();\r\n this.removeFirst();\r\n\r\n if (res.size() == 0 || val != res.tail.data) {\r\n res.addLast(val);\r\n }\r\n }\r\n\r\n this.head = res.head;\r\n this.tail = res.tail;\r\n this.size = res.size;\r\n }\r\n\r\n public void oddEven() {\r\n LinkedList odd = new LinkedList();\r\n LinkedList even = new LinkedList();\r\n\r\n while (this.size > 0) {\r\n int val = this.getFirst();\r\n this.removeFirst();\r\n\r\n if (val % 2 == 0) {\r\n even.addLast(val);\r\n } else {\r\n odd.addLast(val);\r\n }\r\n }\r\n\r\n if (odd.size > 0 && even.size > 0) {\r\n odd.tail.next = even.head;\r\n\r\n this.head = odd.head;\r\n this.tail = even.tail;\r\n this.size = odd.size + even.size;\r\n } else if (odd.size > 0) {\r\n this.head = odd.head;\r\n this.tail = odd.tail;\r\n this.size = odd.size;\r\n } else if (even.size > 0) {\r\n this.head = even.head;\r\n this.tail = even.tail;\r\n this.size = even.size;\r\n }\r\n }\r\n\r\n public void kReverse(int k) {\r\n LinkedList prev = null;\r\n\r\n while (this.size > 0) {\r\n LinkedList curr = new LinkedList();\r\n\r\n if (this.size >= k) {\r\n for (int i = 0; i < k; i++) {\r\n int val = this.getFirst();\r\n this.removeFirst();\r\n curr.addFirst(val);\r\n }\r\n } else {\r\n int sz = this.size;\r\n for (int i = 0; i < sz; i++) {\r\n int val = this.getFirst();\r\n this.removeFirst();\r\n curr.addLast(val);\r\n }\r\n }\r\n\r\n if (prev == null) {\r\n prev = curr;\r\n } else {\r\n prev.tail.next = curr.head;\r\n prev.tail = curr.tail;\r\n prev.size += curr.size;\r\n }\r\n }\r\n\r\n this.head = prev.head;\r\n this.tail = prev.tail;\r\n this.size = prev.size;\r\n }\r\n\r\n private void displayReverseHelper(Node node) {\r\n if (node == null) {\r\n return;\r\n }\r\n displayReverseHelper(node.next);\r\n System.out.print(node.data + \" \");\r\n }\r\n\r\n public void displayReverse() {\r\n displayReverseHelper(head);\r\n System.out.println();\r\n }\r\n\r\n private void reversePRHelper(Node node) {\r\n if (node == tail) {\r\n return;\r\n }\r\n reversePRHelper(node.next);\r\n node.next.next = node;\r\n }\r\n\r\n public void reversePR() {\r\n reversePRHelper(head);\r\n Node temp = head;\r\n head = tail;\r\n tail = temp;\r\n tail.next = null;\r\n }\r\n\r\n public static int findIntersection(LinkedList one, LinkedList two){\r\n // write your code here\r\n }\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int n1 = Integer.parseInt(br.readLine());\r\n LinkedList l1 = new LinkedList();\r\n String[] values1 = br.readLine().split(\" \");\r\n for (int i = 0; i < n1; i++) {\r\n int d = Integer.parseInt(values1[i]);\r\n l1.addLast(d);\r\n }\r\n\r\n int n2 = Integer.parseInt(br.readLine());\r\n LinkedList l2 = new LinkedList();\r\n String[] values2 = br.readLine().split(\" \");\r\n for (int i = 0; i < n2; i++) {\r\n int d = Integer.parseInt(values2[i]);\r\n l2.addLast(d);\r\n }\r\n\r\n int li = Integer.parseInt(br.readLine());\r\n int di = Integer.parseInt(br.readLine());\r\n if(li == 1){\r\n Node n = l1.getNodeAt(di);\r\n l2.tail.next = n;\r\n l2.tail = l1.tail;\r\n l2.size += l1.size - di;\r\n } else {\r\n Node n = l2.getNodeAt(di);\r\n l1.tail.next = n;\r\n l1.tail = l2.tail;\r\n l1.size += l2.size - di;\r\n }\r\n\r\n int inter = LinkedList.findIntersection(l1, l2);\r\n System.out.println(inter);\r\n }\r\n}"},"python":{"code":"class Node(object):\n\n def __init__(self):\n self.data = 0\n self.next = None\n\n\nclass LinkedList(object):\n\n def __init__(self):\n self.head = None\n self.tail = None\n self.size = 0\n\n\n def addLast(self, val):\n temp = Node()\n temp.data = val\n temp.next = None\n\n if self.size == 0:\n self.head = self.tail = temp\n else:\n self.tail.next = temp\n self.tail = temp\n\n self.size += 1\n\n def size(self):\n return self.size\n\n def display(self):\n temp = head\n while temp is not None:\n print(temp.data + \" \", end = '')\n temp = temp.next\n print()\n\n def removeFirst(self):\n if self.size == 0:\n print(\"List is empty\")\n elif self.size == 1:\n self.head = self.tail = None\n self.size = 0\n else:\n self.head = self.head.next\n self.size -= 1\n\n def getFirst(self):\n if self.size == 0:\n print(\"List is empty\")\n return -1\n else:\n return self.head.data\n\n def getLast(self):\n if self.size == 0:\n print(\"List is empty\")\n return -1\n else:\n return self.tail.data\n\n def getAt(self, idx):\n if self.size == 0:\n print(\"List is empty\")\n return -1\n elif idx < 0 or idx >= self.size:\n print(\"Invalid arguments\")\n return -1\n else:\n temp = self.head\n i = 0\n while i < idx:\n temp = temp.next\n i += 1\n return temp.data\n\n def addFirst(self, val):\n temp = Node()\n temp.data = val\n temp.next = self.head\n self.head = temp\n\n if self.size == 0:\n self.tail = temp\n\n self.size += 1\n\n def addAt(self, idx, val):\n if idx < 0 or idx > size:\n print(\"Invalid arguments\")\n elif idx == 0:\n addFirst(val)\n elif idx == size:\n addLast(val)\n else:\n node = Node()\n node.data = val\n\n temp = head\n i = 0\n while i < idx - 1:\n temp = temp.next\n i += 1\n node.next = temp.next\n\n temp.next = node\n size += 1\n\n def removeLast(self):\n if size == 0:\n print(\"List is empty\")\n elif size == 1:\n head = tail = None\n size = 0\n else:\n temp = head\n i = 0\n while i < size - 2:\n temp = temp.next\n i += 1\n\n tail = temp\n tail.next = None\n size -= 1\n\n def removeAt(self, idx):\n if idx < 0 or idx >= size:\n print(\"Invalid arguments\")\n elif idx == 0:\n removeFirst()\n elif idx == size - 1:\n self.removeLast()\n else:\n temp = head\n i = 0\n while i < idx - 1:\n temp = temp.next\n i += 1\n\n temp.next = temp.next.next\n size -= 1\n\n def getNodeAt(self, idx):\n temp = self.head\n i = 0\n while i < idx:\n temp = temp.next\n i += 1\n return temp\n\n def reverseDI(self):\n li = 0\n ri = size - 1\n while li < ri:\n left = self.__getNodeAt(li)\n right = self.__getNodeAt(ri)\n\n temp = left.data\n left.data = right.data\n right.data = temp\n\n li += 1\n ri -= 1\n\n def reversePI(self):\n if size <= 1:\n return\n\n prev = None\n curr = head\n while curr is not None:\n next = curr.next\n\n curr.next = prev\n prev = curr\n curr = next\n\n temp = head\n head = tail\n tail = temp\n\n def kthFromLast(self, k):\n slow = head\n fast = head\n i = 0\n while i < k:\n fast = fast.next\n i += 1\n\n while fast is not tail:\n slow = slow.next\n fast = fast.next\n\n return slow.data\n\n def mid(self):\n f = head\n s = head\n\n while f.next is not None and f.next.next is not None:\n f = f.next.next\n s = s.next\n\n return s.data\n\n @staticmethod\n def mergeTwoSortedLists(l1, l2):\n ml = LinkedList()\n\n one = l1.head\n two = l2.head\n while one is not None and two is not None:\n if one.data < two.data:\n ml.addLast(one.data)\n one = one.next\n else:\n ml.addLast(two.data)\n two = two.next\n\n while one is not None:\n ml.addLast(one.data)\n one = one.next\n\n while two is not None:\n ml.addLast(two.data)\n two = two.next\n\n return ml\n\n @staticmethod\n def midNode(head, tail):\n f = head\n s = head\n\n while f is not tail and f.next is not tail:\n f = f.next.next\n s = s.next\n\n return s\n\n @staticmethod\n def mergeSort(head, tail):\n if head is tail:\n br = LinkedList()\n br.addLast(head.data)\n return br\n\n mid = midNode(head, tail)\n fsh = mergeSort(head, mid)\n ssh = mergeSort(mid.next, tail)\n sl = mergeTwoSortedLists(fsh, ssh)\n return sl\n\n def removeDuplicates(self):\n res = LinkedList()\n\n while self.size() > 0:\n val = self.getFirst()\n self.removeFirst()\n\n if res.size() == 0 or val != res.tail.data:\n res.addLast(val)\n\n self.head = res.head\n self.tail = res.tail\n self.size = res.size\n\n def oddEven(self):\n odd = LinkedList()\n even = LinkedList()\n\n while self.size > 0:\n val = self.getFirst()\n self.removeFirst()\n\n if val % 2 == 0:\n even.addLast(val)\n else:\n odd.addLast(val)\n\n if odd.size > 0 and even.size > 0:\n odd.tail.next = even.head\n\n self.head = odd.head\n self.tail = even.tail\n self.size = odd.size + even.size\n elif odd.size > 0:\n self.head = odd.head\n self.tail = odd.tail\n self.size = odd.size\n elif even.size > 0:\n self.head = even.head\n self.tail = even.tail\n self.size = even.size\n\n def kReverse(self, k):\n prev = None\n\n while self.size > 0:\n curr = LinkedList()\n\n if self.size >= k:\n i = 0\n while i < k:\n val = self.getFirst()\n self.removeFirst()\n curr.addFirst(val)\n i += 1\n else:\n sz = self.size\n i = 0\n while i < sz:\n val = self.getFirst()\n self.removeFirst()\n curr.addLast(val)\n i += 1\n\n if prev is None:\n prev = curr\n else:\n prev.tail.next = curr.head\n prev.tail = curr.tail\n prev.size += curr.size\n\n self.head = prev.head\n self.tail = prev.tail\n self.size = prev.size\n\n def __displayReverseHelper(self, node):\n if node is None:\n return\n self.__displayReverseHelper(node.next)\n print(node.data + \" \", end = '')\n\n def displayReverse(self):\n self.__displayReverseHelper(head)\n print()\n\n def __reversePRHelper(self, node):\n if node is tail:\n return\n self.__reversePRHelper(node.next)\n node.next.next = node\n\n def reversePR(self):\n self.__reversePRHelper(head)\n temp = head\n head = tail\n tail = temp\n tail.next = None\n \n \n def findIntersection(self,one,two):\n // write your code here\n\na_llist1 = LinkedList()\n\nn = int(input())\nvalues = list(map(int,input().split(\" \")))\nfor i in range(n):\n a_llist1.addLast(values[i])\n\na_llist2 = LinkedList()\n\nm = int(input())\nvalues = list(map(int,input().split(\" \")))\nfor i in range(m):\n a_llist2.addLast(values[i])\n\nli = int(input())\ndi = int(input())\n\nif li == 1:\n n = a_llist1.getNodeAt(di)\n\n if a_llist2.size > 0:\n a_llist2.tail.next = n\n else:\n a_llist2.head = n\n\n a_llist2.tail = a_llist1.tail\n a_llist2.size += a_llist1.size - di\nelse:\n n = a_llist2.getNodeAt(di)\n\n if a_llist1.size > 0:\n a_llist1.tail.next = n\n else:\n a_llist1.head = n\n\n a_llist1.tail = a_llist2.tail\n a_llist1.size += a_llist2.size - di\n\ninter = a_llist1.findIntersection(a_llist1, a_llist2)\nprint(inter)"}},"points":10,"difficulty":"easy","sampleInput":"5\r\n1 2 3 4 5\r\n8\r\n11 22 33 44 55 66 77 88\r\n2\r\n3","sampleOutput":"44","questionVideo":"https://www.youtube.com/embed/ZpMQ-Zn6yLc","hints":[],"associated":[{"id":"0184cd65-f233-4cc4-9f1e-84606ca5d0c6","name":"Let variable \"k\" represent the difference between the sizes of the 2 linked lists, and \"n1\" represents the head of the larger linked list, what is the correct way to reach a node in both lists that is equidistant to the intersection point?(Q_ IPL)","slug":"let-variable-k-represent-the-difference-between-the-sizes-of-the-2-linked-lists-and-n1-represents-the-head-of-the-larger-linked-list-what-is-the-correct-way-to-reach-a-node-in-both-lists-that-is-equidistant-to-the-intersection-point-q-ipl","type":4},{"id":"a870996c-761d-4e71-af29-d40d61e4a5ec","name":"What is the space complexity required to solve this question?((Q_ IPL)","slug":"what-is-the-space-complexity-required-to-solve-this-question-q-ipl","type":4},{"id":"d6df18ab-d87f-483c-b559-ec2d2171fc39","name":"Assume that the two lists are of equal size, how do you reach the intersection point, given \"n1\" and \"n2\" as the respective heads of the two lists?(Q_ IPL)","slug":"assume-that-the-two-lists-are-of-equal-size-how-do-you-reach-the-intersection-point-given-n1-and-n2-as-the-respective-heads-of-the-two-lists-q-ipl","type":4},{"id":"ef3f240d-bbc8-4628-aaaa-0856f7574223","name":"It is possible to travel from the tail node and find the intersection point as soon as the next node for both lists is different(Q- IPL)","slug":"it-is-possible-to-travel-from-the-tail-node-and-find-the-intersection-point-as-soon-as-the-next-node-for-both-lists-is-different-q-ipl","type":4}],"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":"91027ef1-2784-45bf-8143-cc6af4560105","name":"Linked Lists For Beginners","slug":"linked-lists-for-beginners","type":0},{"id":"f60d1297-c565-401c-82c1-154421fb4574","name":"Intersection Point Of Linked Lists","slug":"intersection-point-of-linked-lists","type":1}],"next":{"id":"f9561ff9-4769-4604-8e23-caaaa2906d0c","name":"INTERSECTION POINT OF LINKED LISTS","type":3,"slug":"intersection-point-of-linked-lists"},"prev":{"id":"10f8de6d-8b17-4563-bf44-7a296f31236e","name":"Add two linked list","type":3,"slug":"add-two-linked-list-8722"}}}

Intersection Point Of Linked Lists

1. You are given a partially written LinkedList class. 2. You are required to complete the body of findIntersection function. The function is passed two linked lists which start separately but merge at a node and become common thereafter. The function is expected to find the point where two linked lists merge. You are not allowed to use arrays to solve the problem. 3. Input and Output is managed for you. <img src="http://pepcoding.com/resources/ojquestionresource/images/intersection-of-linked-list.jpeg" alt="intersection-of-linked-list">

{"id":"18add11b-4c3e-4198-b2b4-9b502c3ee0c4","name":"Intersection Point Of Linked Lists","description":"1. You are given a partially written LinkedList class.\r\n2. You are required to complete the body of findIntersection function. The function is passed two linked lists which start separately but merge at a node and become common thereafter. The function is expected to find the point where two linked lists merge. You are not allowed to use arrays to solve the problem.\r\n3. Input and Output is managed for you. \r\n\r\n<img src=\"http://pepcoding.com/resources/ojquestionresource/images/intersection-of-linked-list.jpeg\" alt=\"intersection-of-linked-list\">","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1. Time complexity -&gt; O(n)\r\n2. Space complexity -&gt; constant","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <bits/stdc++.h>\n\nusing namespace std;\n\n class Node\n {\n public:\n int data = 0;\n Node *next = nullptr;\n\n Node(int data)\n {\n this->data = data;\n }\n };\n\n\n\nclass linkedlist\n{\n \npublic:\n\n Node *head = nullptr;\n Node *tail = nullptr;\n int size = 0;\n\n //basic->============================================\n\n int size_()\n {\n return this->size;\n }\n\n bool isEmpty()\n {\n return this->size == 0;\n }\n\n string toString()\n {\n Node *curr = this->head;\n string sb = \"\";\n\n while (curr != nullptr)\n {\n sb += to_string(curr->data);\n if (curr->next != nullptr)\n sb += \" \";\n curr = curr->next;\n }\n return sb;\n }\n\n //add->===============================================\nprivate:\n void addFirstNode(Node *node)\n {\n if (this->head == nullptr)\n {\n this->head = node;\n this->tail = node;\n }\n else\n {\n node->next = this->head;\n this->head = node;\n }\n\n this->size++;\n }\n\npublic:\n void addFirst(int val)\n {\n Node *node = new Node(val);\n addFirstNode(node);\n }\n\npublic:\n void addLastNode(Node *node)\n {\n if (this->head == nullptr)\n {\n this->head = node;\n this->tail = node;\n }\n else\n {\n this->tail->next = node;\n this->tail = node;\n }\n\n this->size++;\n }\n\n void addLast(int val)\n {\n Node *node = new Node(val);\n addLastNode(node);\n }\n\n void addNodeAt(Node *node, int idx)\n {\n if (idx == 0)\n addFirstNode(node);\n else if (idx == this->size)\n addLastNode(node);\n else\n {\n Node *prev = getNodeAt(idx - 1);\n Node *curr = prev->next;\n\n prev->next = node;\n curr->next = node;\n\n this->size++;\n }\n }\n\n void addAt(int data, int idx)\n {\n if (idx < 0 || idx > this->size)\n {\n throw(\"invalidLocation: \" + to_string(idx));\n }\n\n Node *node = new Node(data);\n addNodeAt(node, idx);\n }\n\n //remove->============================================\n Node *removeFirstNode()\n {\n Node *node = this->head;\n if (this->size == 1)\n {\n this->head = nullptr;\n this->tail = nullptr;\n }\n else\n {\n this->head = this->head->next;\n node->next = nullptr;\n }\n\n this->size--;\n return node;\n }\n\n int removeFirst(int val)\n {\n if (this->size == 0)\n {\n throw(\"nullptrPointerException: -1\");\n }\n\n Node *node = removeFirstNode();\n int rv = node->data;\n delete node;\n return rv;\n }\n\n Node *removeLastNode()\n {\n Node *node = this->tail;\n if (this->size == 1)\n {\n this->head = nullptr;\n this->tail = nullptr;\n }\n else\n {\n Node *prev = getNodeAt(this->size - 2);\n this->tail = prev;\n prev->next = nullptr;\n }\n\n this->size--;\n return node;\n }\n\n int removeLast(int val)\n {\n if (this->size == 0)\n {\n throw(\"nullptrPointerException: -1\");\n }\n\n Node *node = new Node(val);\n int rv = node->data;\n delete node;\n return rv;\n }\n\n Node *removeNodeAt(int idx)\n {\n if (idx == 0)\n return removeFirstNode();\n else if (idx == this->size - 1)\n return removeLastNode();\n else\n {\n\n Node *prev = getNodeAt(idx - 1);\n Node *curr = prev->next;\n\n prev->next = curr->next;\n curr->next = nullptr;\n\n this->size--;\n return curr;\n }\n }\n\n int removeAt(int idx)\n {\n if (idx < 0 || idx >= this->size)\n {\n throw(\"invalidLocation: \" + idx);\n }\n\n Node *node = removeNodeAt(idx);\n int rv = node->data;\n delete node;\n return rv;\n }\n\n //get->================================================\n Node *getFirstNode()\n {\n return this->head;\n }\n\n int getFirst()\n {\n if (this->size == 0)\n {\n throw(\"nullptrPointerException: -1\");\n }\n\n Node *node = getFirstNode();\n return node->data;\n }\n\n Node *getLastNode()\n {\n return this->tail;\n }\n\n int getLast()\n {\n if (this->size == 0)\n {\n throw(\"nullptrPointerException\");\n }\n\n Node *node = getLastNode();\n return node->data;\n }\n\n Node *getNodeAt(int idx)\n {\n Node *curr = this->head;\n\n while (idx-- > 0)\n {\n curr = curr->next;\n }\n\n return curr;\n }\n\n int getAt(int idx)\n {\n if (idx < 0 || idx >= this->size)\n {\n throw(\"invalidLocation: \" + idx);\n }\n\n Node *node = getNodeAt(idx);\n return node->data;\n }\n};\n\n Node* getMid(Node* head, Node* tail){\n Node* slow = head, *fast = head;\n while(fast->next != tail && fast->next->next != tail){\n fast = fast->next->next;\n slow = slow->next;\n }\n \n return slow;\n }\n\n\n //merge two sorted linkedlist\n linkedlist mergeTwoSortedLists(linkedlist l1, linkedlist l2) {\n linkedlist ans;\n Node* one = l1.head;\n Node* two = l2.head;\n \n while(one != nullptr && two != nullptr){\n if(one->data < two->data){\n ans.addLast(one->data);\n one = one->next;\n }else{\n ans.addLast(two->data);\n two = two->next;\n }\n }\n while(one!=nullptr){\n ans.addLast(one->data);\n one = one->next;\n }\n while(two !=nullptr){\n ans.addLast(two->data);\n two = two->next;\n }\n \n return ans;\n }\n \n linkedlist mergeSort(Node* head,Node* tail ){\n if(head == tail){\n linkedlist base;\n base.addLast(head->data);\n return base;\n }\n \n Node* mid = getMid(head,tail);\n linkedlist fsh = mergeSort(head, mid);\n linkedlist ssh = mergeSort(mid->next, tail);\n \n return mergeTwoSortedLists(fsh,ssh);\n }\n \n int addTwoLists(Node* on, Node* tn, int pio, int pit, linkedlist & res){\n if(on == nullptr && tn == nullptr){\n return 0;\n }\n\n int carry = 0;\n int data = 0;\n if(pio > pit){\n carry = addTwoLists(on->next, tn, pio - 1, pit, res);\n data = carry + on->data;\n } else if(pio < pit){\n carry = addTwoLists(on, tn->next, pio, pit - 1, res);\n data = carry + tn->data;\n } else {\n carry = addTwoLists(on->next, tn->next, pio - 1, pit - 1, res);\n data = carry + on->data + tn->data;\n }\n\n carry = data / 10;\n data = data % 10;\n\n res.addFirst(data);\n return carry;\n }\n\n linkedlist addTwoLists(linkedlist one, linkedlist two) {\n linkedlist res ;\n\n int carry = addTwoLists(one.head, two.head, one.size, two.size, res);\n if(carry > 0){\n res.addFirst(carry);\n }\n\n return res;\n }\n \nlinkedlist makeList() {\n linkedlist l;\n int n1;\n cin >> n1;\n\n for (int i = 0; i < n1; i++) {\n int val;\n cin >> val;\n l.addLast(val);\n }\n return l;\n}\n\n\nint findIntersection(linkedlist one, linkedlist two)\n{\n // write your code here \n}\n\n\nint main()\n{\n\n linkedlist l1= makeList();\n linkedlist l2= makeList();\n int li;\n cin>>li;\n int di;\n cin>>di;\n if (li == 1) {\n Node * n = l1.getNodeAt(di);\n\n if (l2.size > 0) {\n l2.tail->next = n;\n } else {\n l2.head = n;\n }\n\n l2.tail = l1.tail;\n l2.size += l1.size - di;\n } else {\n Node *n = l2.getNodeAt(di);\n\n if (l1.size > 0) {\n l1.tail->next = n;\n } else {\n l1.head = n;\n }\n\n l1.tail = l2.tail;\n l1.size += l2.size - di;\n \n }\n \n \n int s =findIntersection(l1,l2);\n cout <<s<< endl;\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static class Node {\r\n int data;\r\n Node next;\r\n }\r\n\r\n public static class LinkedList {\r\n Node head;\r\n Node tail;\r\n int size;\r\n\r\n void addLast(int val) {\r\n Node temp = new Node();\r\n temp.data = val;\r\n temp.next = null;\r\n\r\n if (size == 0) {\r\n head = tail = temp;\r\n } else {\r\n tail.next = temp;\r\n tail = temp;\r\n }\r\n\r\n size++;\r\n }\r\n\r\n public int size() {\r\n return size;\r\n }\r\n\r\n public void display() {\r\n for (Node temp = head; temp != null; temp = temp.next) {\r\n System.out.print(temp.data + \" \");\r\n }\r\n System.out.println();\r\n }\r\n\r\n public void removeFirst() {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n } else if (size == 1) {\r\n head = tail = null;\r\n size = 0;\r\n } else {\r\n head = head.next;\r\n size--;\r\n }\r\n }\r\n\r\n public int getFirst() {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n return -1;\r\n } else {\r\n return head.data;\r\n }\r\n }\r\n\r\n public int getLast() {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n return -1;\r\n } else {\r\n return tail.data;\r\n }\r\n }\r\n\r\n public int getAt(int idx) {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n return -1;\r\n } else if (idx < 0 || idx >= size) {\r\n System.out.println(\"Invalid arguments\");\r\n return -1;\r\n } else {\r\n Node temp = head;\r\n for (int i = 0; i < idx; i++) {\r\n temp = temp.next;\r\n }\r\n return temp.data;\r\n }\r\n }\r\n\r\n public void addFirst(int val) {\r\n Node temp = new Node();\r\n temp.data = val;\r\n temp.next = head;\r\n head = temp;\r\n\r\n if (size == 0) {\r\n tail = temp;\r\n }\r\n\r\n size++;\r\n }\r\n\r\n public void addAt(int idx, int val) {\r\n if (idx < 0 || idx > size) {\r\n System.out.println(\"Invalid arguments\");\r\n } else if (idx == 0) {\r\n addFirst(val);\r\n } else if (idx == size) {\r\n addLast(val);\r\n } else {\r\n Node node = new Node();\r\n node.data = val;\r\n\r\n Node temp = head;\r\n for (int i = 0; i < idx - 1; i++) {\r\n temp = temp.next;\r\n }\r\n node.next = temp.next;\r\n\r\n temp.next = node;\r\n size++;\r\n }\r\n }\r\n\r\n public void removeLast() {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n } else if (size == 1) {\r\n head = tail = null;\r\n size = 0;\r\n } else {\r\n Node temp = head;\r\n for (int i = 0; i < size - 2; i++) {\r\n temp = temp.next;\r\n }\r\n\r\n tail = temp;\r\n tail.next = null;\r\n size--;\r\n }\r\n }\r\n\r\n public void removeAt(int idx) {\r\n if (idx < 0 || idx >= size) {\r\n System.out.println(\"Invalid arguments\");\r\n } else if (idx == 0) {\r\n removeFirst();\r\n } else if (idx == size - 1) {\r\n removeLast();\r\n } else {\r\n Node temp = head;\r\n for (int i = 0; i < idx - 1; i++) {\r\n temp = temp.next;\r\n }\r\n\r\n temp.next = temp.next.next;\r\n size--;\r\n }\r\n }\r\n\r\n private Node getNodeAt(int idx) {\r\n Node temp = head;\r\n for (int i = 0; i < idx; i++) {\r\n temp = temp.next;\r\n }\r\n return temp;\r\n }\r\n\r\n public void reverseDI() {\r\n int li = 0;\r\n int ri = size - 1;\r\n while (li < ri) {\r\n Node left = getNodeAt(li);\r\n Node right = getNodeAt(ri);\r\n\r\n int temp = left.data;\r\n left.data = right.data;\r\n right.data = temp;\r\n\r\n li++;\r\n ri--;\r\n }\r\n }\r\n\r\n public void reversePI() {\r\n if (size <= 1) {\r\n return;\r\n }\r\n\r\n Node prev = null;\r\n Node curr = head;\r\n while (curr != null) {\r\n Node next = curr.next;\r\n\r\n curr.next = prev;\r\n prev = curr;\r\n curr = next;\r\n }\r\n\r\n Node temp = head;\r\n head = tail;\r\n tail = temp;\r\n }\r\n\r\n public int kthFromLast(int k) {\r\n Node slow = head;\r\n Node fast = head;\r\n for (int i = 0; i < k; i++) {\r\n fast = fast.next;\r\n }\r\n\r\n while (fast != tail) {\r\n slow = slow.next;\r\n fast = fast.next;\r\n }\r\n\r\n return slow.data;\r\n }\r\n\r\n public int mid() {\r\n Node f = head;\r\n Node s = head;\r\n\r\n while (f.next != null && f.next.next != null) {\r\n f = f.next.next;\r\n s = s.next;\r\n }\r\n\r\n return s.data;\r\n }\r\n\r\n public static LinkedList mergeTwoSortedLists(LinkedList l1, LinkedList l2) {\r\n LinkedList ml = new LinkedList();\r\n\r\n Node one = l1.head;\r\n Node two = l2.head;\r\n while (one != null && two != null) {\r\n if (one.data < two.data) {\r\n ml.addLast(one.data);\r\n one = one.next;\r\n } else {\r\n ml.addLast(two.data);\r\n two = two.next;\r\n }\r\n }\r\n\r\n while (one != null) {\r\n ml.addLast(one.data);\r\n one = one.next;\r\n }\r\n\r\n while (two != null) {\r\n ml.addLast(two.data);\r\n two = two.next;\r\n }\r\n\r\n return ml;\r\n }\r\n\r\n public static Node midNode(Node head, Node tail) {\r\n Node f = head;\r\n Node s = head;\r\n\r\n while (f != tail && f.next != tail) {\r\n f = f.next.next;\r\n s = s.next;\r\n }\r\n\r\n return s;\r\n }\r\n\r\n public static LinkedList mergeSort(Node head, Node tail) {\r\n if (head == tail) {\r\n LinkedList br = new LinkedList();\r\n br.addLast(head.data);\r\n return br;\r\n }\r\n\r\n Node mid = midNode(head, tail);\r\n LinkedList fsh = mergeSort(head, mid);\r\n LinkedList ssh = mergeSort(mid.next, tail);\r\n LinkedList sl = mergeTwoSortedLists(fsh, ssh);\r\n return sl;\r\n }\r\n\r\n public void removeDuplicates() {\r\n LinkedList res = new LinkedList();\r\n\r\n while (this.size() > 0) {\r\n int val = this.getFirst();\r\n this.removeFirst();\r\n\r\n if (res.size() == 0 || val != res.tail.data) {\r\n res.addLast(val);\r\n }\r\n }\r\n\r\n this.head = res.head;\r\n this.tail = res.tail;\r\n this.size = res.size;\r\n }\r\n\r\n public void oddEven() {\r\n LinkedList odd = new LinkedList();\r\n LinkedList even = new LinkedList();\r\n\r\n while (this.size > 0) {\r\n int val = this.getFirst();\r\n this.removeFirst();\r\n\r\n if (val % 2 == 0) {\r\n even.addLast(val);\r\n } else {\r\n odd.addLast(val);\r\n }\r\n }\r\n\r\n if (odd.size > 0 && even.size > 0) {\r\n odd.tail.next = even.head;\r\n\r\n this.head = odd.head;\r\n this.tail = even.tail;\r\n this.size = odd.size + even.size;\r\n } else if (odd.size > 0) {\r\n this.head = odd.head;\r\n this.tail = odd.tail;\r\n this.size = odd.size;\r\n } else if (even.size > 0) {\r\n this.head = even.head;\r\n this.tail = even.tail;\r\n this.size = even.size;\r\n }\r\n }\r\n\r\n public void kReverse(int k) {\r\n LinkedList prev = null;\r\n\r\n while (this.size > 0) {\r\n LinkedList curr = new LinkedList();\r\n\r\n if (this.size >= k) {\r\n for (int i = 0; i < k; i++) {\r\n int val = this.getFirst();\r\n this.removeFirst();\r\n curr.addFirst(val);\r\n }\r\n } else {\r\n int sz = this.size;\r\n for (int i = 0; i < sz; i++) {\r\n int val = this.getFirst();\r\n this.removeFirst();\r\n curr.addLast(val);\r\n }\r\n }\r\n\r\n if (prev == null) {\r\n prev = curr;\r\n } else {\r\n prev.tail.next = curr.head;\r\n prev.tail = curr.tail;\r\n prev.size += curr.size;\r\n }\r\n }\r\n\r\n this.head = prev.head;\r\n this.tail = prev.tail;\r\n this.size = prev.size;\r\n }\r\n\r\n private void displayReverseHelper(Node node) {\r\n if (node == null) {\r\n return;\r\n }\r\n displayReverseHelper(node.next);\r\n System.out.print(node.data + \" \");\r\n }\r\n\r\n public void displayReverse() {\r\n displayReverseHelper(head);\r\n System.out.println();\r\n }\r\n\r\n private void reversePRHelper(Node node) {\r\n if (node == tail) {\r\n return;\r\n }\r\n reversePRHelper(node.next);\r\n node.next.next = node;\r\n }\r\n\r\n public void reversePR() {\r\n reversePRHelper(head);\r\n Node temp = head;\r\n head = tail;\r\n tail = temp;\r\n tail.next = null;\r\n }\r\n\r\n public static int findIntersection(LinkedList one, LinkedList two){\r\n // write your code here\r\n }\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int n1 = Integer.parseInt(br.readLine());\r\n LinkedList l1 = new LinkedList();\r\n String[] values1 = br.readLine().split(\" \");\r\n for (int i = 0; i < n1; i++) {\r\n int d = Integer.parseInt(values1[i]);\r\n l1.addLast(d);\r\n }\r\n\r\n int n2 = Integer.parseInt(br.readLine());\r\n LinkedList l2 = new LinkedList();\r\n String[] values2 = br.readLine().split(\" \");\r\n for (int i = 0; i < n2; i++) {\r\n int d = Integer.parseInt(values2[i]);\r\n l2.addLast(d);\r\n }\r\n\r\n int li = Integer.parseInt(br.readLine());\r\n int di = Integer.parseInt(br.readLine());\r\n if(li == 1){\r\n Node n = l1.getNodeAt(di);\r\n l2.tail.next = n;\r\n l2.tail = l1.tail;\r\n l2.size += l1.size - di;\r\n } else {\r\n Node n = l2.getNodeAt(di);\r\n l1.tail.next = n;\r\n l1.tail = l2.tail;\r\n l1.size += l2.size - di;\r\n }\r\n\r\n int inter = LinkedList.findIntersection(l1, l2);\r\n System.out.println(inter);\r\n }\r\n}"},"python":{"code":"class Node(object):\n\n def __init__(self):\n self.data = 0\n self.next = None\n\n\nclass LinkedList(object):\n\n def __init__(self):\n self.head = None\n self.tail = None\n self.size = 0\n\n\n def addLast(self, val):\n temp = Node()\n temp.data = val\n temp.next = None\n\n if self.size == 0:\n self.head = self.tail = temp\n else:\n self.tail.next = temp\n self.tail = temp\n\n self.size += 1\n\n def size(self):\n return self.size\n\n def display(self):\n temp = head\n while temp is not None:\n print(temp.data + \" \", end = '')\n temp = temp.next\n print()\n\n def removeFirst(self):\n if self.size == 0:\n print(\"List is empty\")\n elif self.size == 1:\n self.head = self.tail = None\n self.size = 0\n else:\n self.head = self.head.next\n self.size -= 1\n\n def getFirst(self):\n if self.size == 0:\n print(\"List is empty\")\n return -1\n else:\n return self.head.data\n\n def getLast(self):\n if self.size == 0:\n print(\"List is empty\")\n return -1\n else:\n return self.tail.data\n\n def getAt(self, idx):\n if self.size == 0:\n print(\"List is empty\")\n return -1\n elif idx < 0 or idx >= self.size:\n print(\"Invalid arguments\")\n return -1\n else:\n temp = self.head\n i = 0\n while i < idx:\n temp = temp.next\n i += 1\n return temp.data\n\n def addFirst(self, val):\n temp = Node()\n temp.data = val\n temp.next = self.head\n self.head = temp\n\n if self.size == 0:\n self.tail = temp\n\n self.size += 1\n\n def addAt(self, idx, val):\n if idx < 0 or idx > size:\n print(\"Invalid arguments\")\n elif idx == 0:\n addFirst(val)\n elif idx == size:\n addLast(val)\n else:\n node = Node()\n node.data = val\n\n temp = head\n i = 0\n while i < idx - 1:\n temp = temp.next\n i += 1\n node.next = temp.next\n\n temp.next = node\n size += 1\n\n def removeLast(self):\n if size == 0:\n print(\"List is empty\")\n elif size == 1:\n head = tail = None\n size = 0\n else:\n temp = head\n i = 0\n while i < size - 2:\n temp = temp.next\n i += 1\n\n tail = temp\n tail.next = None\n size -= 1\n\n def removeAt(self, idx):\n if idx < 0 or idx >= size:\n print(\"Invalid arguments\")\n elif idx == 0:\n removeFirst()\n elif idx == size - 1:\n self.removeLast()\n else:\n temp = head\n i = 0\n while i < idx - 1:\n temp = temp.next\n i += 1\n\n temp.next = temp.next.next\n size -= 1\n\n def getNodeAt(self, idx):\n temp = self.head\n i = 0\n while i < idx:\n temp = temp.next\n i += 1\n return temp\n\n def reverseDI(self):\n li = 0\n ri = size - 1\n while li < ri:\n left = self.__getNodeAt(li)\n right = self.__getNodeAt(ri)\n\n temp = left.data\n left.data = right.data\n right.data = temp\n\n li += 1\n ri -= 1\n\n def reversePI(self):\n if size <= 1:\n return\n\n prev = None\n curr = head\n while curr is not None:\n next = curr.next\n\n curr.next = prev\n prev = curr\n curr = next\n\n temp = head\n head = tail\n tail = temp\n\n def kthFromLast(self, k):\n slow = head\n fast = head\n i = 0\n while i < k:\n fast = fast.next\n i += 1\n\n while fast is not tail:\n slow = slow.next\n fast = fast.next\n\n return slow.data\n\n def mid(self):\n f = head\n s = head\n\n while f.next is not None and f.next.next is not None:\n f = f.next.next\n s = s.next\n\n return s.data\n\n @staticmethod\n def mergeTwoSortedLists(l1, l2):\n ml = LinkedList()\n\n one = l1.head\n two = l2.head\n while one is not None and two is not None:\n if one.data < two.data:\n ml.addLast(one.data)\n one = one.next\n else:\n ml.addLast(two.data)\n two = two.next\n\n while one is not None:\n ml.addLast(one.data)\n one = one.next\n\n while two is not None:\n ml.addLast(two.data)\n two = two.next\n\n return ml\n\n @staticmethod\n def midNode(head, tail):\n f = head\n s = head\n\n while f is not tail and f.next is not tail:\n f = f.next.next\n s = s.next\n\n return s\n\n @staticmethod\n def mergeSort(head, tail):\n if head is tail:\n br = LinkedList()\n br.addLast(head.data)\n return br\n\n mid = midNode(head, tail)\n fsh = mergeSort(head, mid)\n ssh = mergeSort(mid.next, tail)\n sl = mergeTwoSortedLists(fsh, ssh)\n return sl\n\n def removeDuplicates(self):\n res = LinkedList()\n\n while self.size() > 0:\n val = self.getFirst()\n self.removeFirst()\n\n if res.size() == 0 or val != res.tail.data:\n res.addLast(val)\n\n self.head = res.head\n self.tail = res.tail\n self.size = res.size\n\n def oddEven(self):\n odd = LinkedList()\n even = LinkedList()\n\n while self.size > 0:\n val = self.getFirst()\n self.removeFirst()\n\n if val % 2 == 0:\n even.addLast(val)\n else:\n odd.addLast(val)\n\n if odd.size > 0 and even.size > 0:\n odd.tail.next = even.head\n\n self.head = odd.head\n self.tail = even.tail\n self.size = odd.size + even.size\n elif odd.size > 0:\n self.head = odd.head\n self.tail = odd.tail\n self.size = odd.size\n elif even.size > 0:\n self.head = even.head\n self.tail = even.tail\n self.size = even.size\n\n def kReverse(self, k):\n prev = None\n\n while self.size > 0:\n curr = LinkedList()\n\n if self.size >= k:\n i = 0\n while i < k:\n val = self.getFirst()\n self.removeFirst()\n curr.addFirst(val)\n i += 1\n else:\n sz = self.size\n i = 0\n while i < sz:\n val = self.getFirst()\n self.removeFirst()\n curr.addLast(val)\n i += 1\n\n if prev is None:\n prev = curr\n else:\n prev.tail.next = curr.head\n prev.tail = curr.tail\n prev.size += curr.size\n\n self.head = prev.head\n self.tail = prev.tail\n self.size = prev.size\n\n def __displayReverseHelper(self, node):\n if node is None:\n return\n self.__displayReverseHelper(node.next)\n print(node.data + \" \", end = '')\n\n def displayReverse(self):\n self.__displayReverseHelper(head)\n print()\n\n def __reversePRHelper(self, node):\n if node is tail:\n return\n self.__reversePRHelper(node.next)\n node.next.next = node\n\n def reversePR(self):\n self.__reversePRHelper(head)\n temp = head\n head = tail\n tail = temp\n tail.next = None\n \n \n def findIntersection(self,one,two):\n // write your code here\n\na_llist1 = LinkedList()\n\nn = int(input())\nvalues = list(map(int,input().split(\" \")))\nfor i in range(n):\n a_llist1.addLast(values[i])\n\na_llist2 = LinkedList()\n\nm = int(input())\nvalues = list(map(int,input().split(\" \")))\nfor i in range(m):\n a_llist2.addLast(values[i])\n\nli = int(input())\ndi = int(input())\n\nif li == 1:\n n = a_llist1.getNodeAt(di)\n\n if a_llist2.size > 0:\n a_llist2.tail.next = n\n else:\n a_llist2.head = n\n\n a_llist2.tail = a_llist1.tail\n a_llist2.size += a_llist1.size - di\nelse:\n n = a_llist2.getNodeAt(di)\n\n if a_llist1.size > 0:\n a_llist1.tail.next = n\n else:\n a_llist1.head = n\n\n a_llist1.tail = a_llist2.tail\n a_llist1.size += a_llist2.size - di\n\ninter = a_llist1.findIntersection(a_llist1, a_llist2)\nprint(inter)"}},"points":10,"difficulty":"easy","sampleInput":"5\r\n1 2 3 4 5\r\n8\r\n11 22 33 44 55 66 77 88\r\n2\r\n3","sampleOutput":"44","questionVideo":"https://www.youtube.com/embed/ZpMQ-Zn6yLc","hints":[],"associated":[{"id":"0184cd65-f233-4cc4-9f1e-84606ca5d0c6","name":"Let variable \"k\" represent the difference between the sizes of the 2 linked lists, and \"n1\" represents the head of the larger linked list, what is the correct way to reach a node in both lists that is equidistant to the intersection point?(Q_ IPL)","slug":"let-variable-k-represent-the-difference-between-the-sizes-of-the-2-linked-lists-and-n1-represents-the-head-of-the-larger-linked-list-what-is-the-correct-way-to-reach-a-node-in-both-lists-that-is-equidistant-to-the-intersection-point-q-ipl","type":4},{"id":"a870996c-761d-4e71-af29-d40d61e4a5ec","name":"What is the space complexity required to solve this question?((Q_ IPL)","slug":"what-is-the-space-complexity-required-to-solve-this-question-q-ipl","type":4},{"id":"d6df18ab-d87f-483c-b559-ec2d2171fc39","name":"Assume that the two lists are of equal size, how do you reach the intersection point, given \"n1\" and \"n2\" as the respective heads of the two lists?(Q_ IPL)","slug":"assume-that-the-two-lists-are-of-equal-size-how-do-you-reach-the-intersection-point-given-n1-and-n2-as-the-respective-heads-of-the-two-lists-q-ipl","type":4},{"id":"ef3f240d-bbc8-4628-aaaa-0856f7574223","name":"It is possible to travel from the tail node and find the intersection point as soon as the next node for both lists is different(Q- IPL)","slug":"it-is-possible-to-travel-from-the-tail-node-and-find-the-intersection-point-as-soon-as-the-next-node-for-both-lists-is-different-q-ipl","type":4}],"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":"91027ef1-2784-45bf-8143-cc6af4560105","name":"Linked Lists For Beginners","slug":"linked-lists-for-beginners","type":0},{"id":"f60d1297-c565-401c-82c1-154421fb4574","name":"Intersection Point Of Linked Lists","slug":"intersection-point-of-linked-lists","type":1}],"next":{"id":"f9561ff9-4769-4604-8e23-caaaa2906d0c","name":"INTERSECTION POINT OF LINKED LISTS","type":3,"slug":"intersection-point-of-linked-lists"},"prev":{"id":"10f8de6d-8b17-4563-bf44-7a296f31236e","name":"Add two linked list","type":3,"slug":"add-two-linked-list-8722"}}}
plane

Editor

Loading...

Intersection Point Of Linked Lists

easy

1. You are given a partially written LinkedList class. 2. You are required to complete the body of findIntersection function. The function is passed two linked lists which start separately but merge at a node and become common thereafter. The function is expected to find the point where two linked lists merge. You are not allowed to use arrays to solve the problem. 3. Input and Output is managed for you. intersection-of-linked-list

Constraints

1. Time complexity -> O(n) 2. Space complexity -> constant

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

5 1 2 3 4 5 8 11 22 33 44 55 66 77 88 2 3

Sample Output

44

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode