{"id":"ecc85a9c-b089-4a63-9e1a-947a5c0f233d","name":"Add Two Linked Lists","description":"1. You are given a partially written LinkedList class.\r\n2. You are required to complete the body of addLinkedLists function. The function is passed two linked lists which represent two numbers - the first element is the most significant digit and the last element is the least significant digit. The function is expected to add the two linked list and return a new linked list.\r\n\r\nThe following approaches are not allowed :\r\n 1. Don't reverse the linked lists in order to access them from least significant digit \r\n to most significant.\r\n 2. Don't use arrays or explicit extra memory.\r\n 3. Don't convert linked lists to number, add them up and convert the result back \r\n to a linked list.\r\n\r\nHint - You are expected to take help of recursion to access digits from least significant to most significant. You have to tackle the challenge of unequal size of lists and manage carry where required.\r\n\r\n3. Input and Output is managed for you. \r\n\r\nNote-> Make sure to set head and tail appropriately because addFirst and addLast has been used to test their values in the input-output code.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1. Time complexity -&gt; O(n)\r\n2. Space complexity -&gt; Recursion space, O(n)","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 \n\n linkedlist addTwoLists(linkedlist one, linkedlist two) {\n // write your code here\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\nint main()\n{\n linkedlist l= makeList();\n linkedlist m= makeList();\n int a;\n cin>>a;\n int b;\n cin>>b;\n linkedlist res= addTwoLists(l,m);\n cout << l.toString() << endl;\n cout << m.toString() << endl;\n cout << res.toString() << endl;\n res.addFirst(a);\n res.addLast(b);\n cout << res.toString() << 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 LinkedList addTwoLists(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 LinkedList sum = LinkedList.addTwoLists(l1, l2);\r\n\r\n int a = Integer.parseInt(br.readLine());\r\n int b = Integer.parseInt(br.readLine());\r\n\r\n l1.display();\r\n l2.display();\r\n sum.display();\r\n sum.addFirst(a);\r\n sum.addLast(b);\r\n sum.display();\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 = self.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 = 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 addTwoLists(self,one, two):\n\n # write your code here\n \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\na = int(input())\nb = int(input())\n\nsum=LinkedList()\nsum = a_llist1.addTwoLists(a_llist1, a_llist2)\n\n\na_llist1.display()\na_llist2.display()\nsum.display()\nsum.addFirst(a)\nsum.addLast(b)\nsum.display()"}},"points":10,"difficulty":"easy","sampleInput":"1\r\n1\r\n3\r\n9 9 9\r\n10\r\n20","sampleOutput":"1 \r\n9 9 9 \r\n1 0 0 0 \r\n10 1 0 0 0 20 \r\n","questionVideo":"https://www.youtube.com/embed/EmlJIS1K7tk","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":"91027ef1-2784-45bf-8143-cc6af4560105","name":"Linked Lists For Beginners","slug":"linked-lists-for-beginners","type":0},{"id":"b8209838-570a-4166-b764-d79850c07be0","name":"Add Two Linked Lists","slug":"add-two-linked-lists","type":1}],"next":{"id":"10f8de6d-8b17-4563-bf44-7a296f31236e","name":"Add two linked list","type":3,"slug":"add-two-linked-list-8722"},"prev":{"id":"5632da27-deb5-480c-8668-2b2ae2ea5296","name":"Fold A Linked List","type":3,"slug":"fold-a-linked-list"}}}

Add Two Linked Lists

1. You are given a partially written LinkedList class. 2. You are required to complete the body of addLinkedLists function. The function is passed two linked lists which represent two numbers - the first element is the most significant digit and the last element is the least significant digit. The function is expected to add the two linked list and return a new linked list. The following approaches are not allowed : 1. Don't reverse the linked lists in order to access them from least significant digit to most significant. 2. Don't use arrays or explicit extra memory. 3. Don't convert linked lists to number, add them up and convert the result back to a linked list. Hint - You are expected to take help of recursion to access digits from least significant to most significant. You have to tackle the challenge of unequal size of lists and manage carry where required. 3. Input and Output is managed for you. Note-> Make sure to set head and tail appropriately because addFirst and addLast has been used to test their values in the input-output code.

{"id":"ecc85a9c-b089-4a63-9e1a-947a5c0f233d","name":"Add Two Linked Lists","description":"1. You are given a partially written LinkedList class.\r\n2. You are required to complete the body of addLinkedLists function. The function is passed two linked lists which represent two numbers - the first element is the most significant digit and the last element is the least significant digit. The function is expected to add the two linked list and return a new linked list.\r\n\r\nThe following approaches are not allowed :\r\n 1. Don't reverse the linked lists in order to access them from least significant digit \r\n to most significant.\r\n 2. Don't use arrays or explicit extra memory.\r\n 3. Don't convert linked lists to number, add them up and convert the result back \r\n to a linked list.\r\n\r\nHint - You are expected to take help of recursion to access digits from least significant to most significant. You have to tackle the challenge of unequal size of lists and manage carry where required.\r\n\r\n3. Input and Output is managed for you. \r\n\r\nNote-> Make sure to set head and tail appropriately because addFirst and addLast has been used to test their values in the input-output code.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1. Time complexity -&gt; O(n)\r\n2. Space complexity -&gt; Recursion space, O(n)","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 \n\n linkedlist addTwoLists(linkedlist one, linkedlist two) {\n // write your code here\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\nint main()\n{\n linkedlist l= makeList();\n linkedlist m= makeList();\n int a;\n cin>>a;\n int b;\n cin>>b;\n linkedlist res= addTwoLists(l,m);\n cout << l.toString() << endl;\n cout << m.toString() << endl;\n cout << res.toString() << endl;\n res.addFirst(a);\n res.addLast(b);\n cout << res.toString() << 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 LinkedList addTwoLists(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 LinkedList sum = LinkedList.addTwoLists(l1, l2);\r\n\r\n int a = Integer.parseInt(br.readLine());\r\n int b = Integer.parseInt(br.readLine());\r\n\r\n l1.display();\r\n l2.display();\r\n sum.display();\r\n sum.addFirst(a);\r\n sum.addLast(b);\r\n sum.display();\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 = self.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 = 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 addTwoLists(self,one, two):\n\n # write your code here\n \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\na = int(input())\nb = int(input())\n\nsum=LinkedList()\nsum = a_llist1.addTwoLists(a_llist1, a_llist2)\n\n\na_llist1.display()\na_llist2.display()\nsum.display()\nsum.addFirst(a)\nsum.addLast(b)\nsum.display()"}},"points":10,"difficulty":"easy","sampleInput":"1\r\n1\r\n3\r\n9 9 9\r\n10\r\n20","sampleOutput":"1 \r\n9 9 9 \r\n1 0 0 0 \r\n10 1 0 0 0 20 \r\n","questionVideo":"https://www.youtube.com/embed/EmlJIS1K7tk","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":"91027ef1-2784-45bf-8143-cc6af4560105","name":"Linked Lists For Beginners","slug":"linked-lists-for-beginners","type":0},{"id":"b8209838-570a-4166-b764-d79850c07be0","name":"Add Two Linked Lists","slug":"add-two-linked-lists","type":1}],"next":{"id":"10f8de6d-8b17-4563-bf44-7a296f31236e","name":"Add two linked list","type":3,"slug":"add-two-linked-list-8722"},"prev":{"id":"5632da27-deb5-480c-8668-2b2ae2ea5296","name":"Fold A Linked List","type":3,"slug":"fold-a-linked-list"}}}
plane

Editor

Loading...

Add Two Linked Lists

easy

1. You are given a partially written LinkedList class. 2. You are required to complete the body of addLinkedLists function. The function is passed two linked lists which represent two numbers - the first element is the most significant digit and the last element is the least significant digit. The function is expected to add the two linked list and return a new linked list. The following approaches are not allowed : 1. Don't reverse the linked lists in order to access them from least significant digit to most significant. 2. Don't use arrays or explicit extra memory. 3. Don't convert linked lists to number, add them up and convert the result back to a linked list. Hint - You are expected to take help of recursion to access digits from least significant to most significant. You have to tackle the challenge of unequal size of lists and manage carry where required. 3. Input and Output is managed for you. Note-> Make sure to set head and tail appropriately because addFirst and addLast has been used to test their values in the input-output code.

Constraints

1. Time complexity -> O(n) 2. Space complexity -> Recursion space, O(n)

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

1 1 3 9 9 9 10 20

Sample Output

1 9 9 9 1 0 0 0 10 1 0 0 0 20

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode