pdog1111 Recursive solution is nice and neat. Linked lists are often naturally handled recursively:
Node Delete(Node head, int position) { if (position == 0){ return head.next; } head.next = Delete(head.next, position-1); return head; }
sidnshady but doesn't this just return the list with all the succesor elements of the element to be deleted?
kotulakk 3 months late, but no. It will keep recursively calling itself until position == 0. It won't actually delete anything but the node at the target index.
peeyushch01 [deleted]
ankur_sharma Good One patrick. Runs smoothly. Keep contributing bro.
funky24426 why is this downwoted lol.
adelin_ghanayem whenever I think I've got something cool I always find something better but this is the essence of life, nice solution !
signonsridhar Works like a charm
rafa_fr Very nice the code!
But I have a question: what if the head parameter is null?
Would it be thrown a NullPointerException?
jtlang You're right!
However, the Input Format description forbids this case. The key line is:
"position will always be at least 0 and less than the number of the elements in the list." (i.e. 0 <= position < length).
Assume the head is null. This means there are 0 elements in the list. Thus, position < length = 0. Since we know position >= 0, this is a contradiction. So in a valid input, the head cannot be null.
Additionally, when position > 0, Delete is called recursively. In the recursive subproblem created, both position and the number of elements are decreased by 1. In the current call, we know 0 < position < length. This implies 0 <= (position - 1) < (length - 1). So the parameters to the recursive call will be valid inputs too.
TLDR: The requirement that position < length implies that position will always reach 0 before length does (which is when head would become null).
elast Error occurs in the case of a deep recursive process.
pirimiri nice, took me 10-15 min to figure it out though...
addisuhg looks nice except performance issue ... for N position, recursive will create N number of functions ...
Kartar Explain this please..
lakshay1 chal beeeeee
thrinath999 Nice one!
aanandsw [deleted]danman1979 As others have said, this could be problematic if the list is very long and the deleted node is near the end of the list. You could possibly run out of stack space with all the recursive calls. That's just something to keep in mind.
desaim Good point. Always a drawback of writing a recursive solution. Only seems to be suitable for 'divide and conquer' problems.
max_waser Not sure if you're still active after 2 years, but I've a question:
If the list is long enough that the stack size could be a problem, wouldn't a singly linked list be inefficient by nature? If that's the case, it would be safe to assume the list is indeed short enough for a recursive solution.
Or are its benefits (simplicity, speed of adding a node at either end) enough to still make it a desirable option?
shortcut2alireza It is only returning the node not really deleting anything. Consider this scenario: LinkedList with only one node: Head. if we call the delete fucntion with position =0, the function will return null, but the head is still there. So if you go back and want to do any operations on the LinkedList, it wont be an empty list. It will have a head node in there.
MIC0DE can you please explain how does the target node is deleted??
shortcut2alireza 1-You have to make sure the target node does not refrence anything. FOr exmaple if head is the target node, make head to point to the second element. By doing this, in Java, teh garbage colector will delete that target for you (asumming nothing else is pointing to it). In C++ you have to actulay write a delete stametmen to delete the node.
2- make sure nothing else is pointing to the target. If the target is the second node, you have to make sure head points to the 3rd node...
It is just pointers.
flmserdfr im pretty sure this wouldnt work. you abandon all the elements prior to the deletion element
satyajit02 Nice solutions! Here was my solution-
Node Delete(Node head, int position) { if (position == 0) { return head.next; } Node currentNode = head; Node prevNode = head; for (int i = 0; i < position; i++) { prevNode = currentNode; if (currentNode.next == null) { break; } currentNode = currentNode.next; } prevNode.next = currentNode.next; return head; }
Later I changed it to this-
Node Delete(Node head, int position) { if (position > 0 && head.next == null) { return head; } if (position == 0 || head.next == null) { return head.next; } head.next = Delete(head.next, position - 1); return head; }
Which can delete the last element as well as can ignore delete operation which position is > ListSize.
bhavgothadiya Nice One
RodneyShag Cool recursion. However, this recursion requires O(n) space. You can solve this problem iteratively like this in O(1) space.
From my HackerRank solutions.
elast Thank you for giving me advice. Is it okay with a source like this?
RodneyShag Sorry I don't understand your question. The source I linked to is the space efficient solution that works.
elast Oh, is that talk of the number of lines of the editor?
If I meet,The address by which well has secured c++ for a heap area by the new function. When becoming unnecessary, you have to eliminate using the delete function specifically. When not doing that temporarily, a memory will be leaked.
It's processed automatically in GC in java.
It's inevitable by this, than java. A cord of c++ becomes redundant.
RodneyShag Hi. I'm not talking about the number of lines of the editor. By space efficiency, I just mean it takes O(1) space for the function since I only store 1 variable.
elast I'm sorry I lost sending comments. I finally understood the meaning of the word you are saying. I rewrote it with reference to your advice, but under this condition it is the limit to reduce the number of variables down to two. If you can use smart pointers, you can only have one variable as you say.
Although I am using google translation, I feel that translated English is wrong, I am worried whether it will succeed.
Xcadet Hello, how does returning the head works when nothing is assigned to it in the last else block?
ankita_r_pawar Nice one....Thanks a ton....
reidhymes Just to clear up any confusion, the above solution has memory leaks. This solution does not deallocate the memory of the node at the target index.
This is the C++ solution with memory cleanup:
Node* Delete(Node *head, int position) { if (position == 0) { auto next = head->next; delete head; return next; } head->next = Delete(head->next, position - 1); return head; }
ujjwalsaxena My approach in Java.. I am a C# guy. C# was not available so tried this.
Node Delete(Node head, int position) { Node temp=head; int pos=1; if(position==0) return head.next; while(pos<position) { head=head.next; pos++; } head.next=head.next.next; return temp; }
cybosser You forgot to free the memory occupied by a node being deleted.
vishalchanda_vc1 how to free the free memory occupied by a node in java?
RodneyShag You don't have to free memory in Java. It is done automatically and is called garbage collection.
muralithatholu71 in "c"..free("desired node")...this function can be used to free the memory
sayanarijit Cool.. python version:
def Delete(head, position): if position == 0: return head.next head.next = Delete(head.next, position-1) return head
rudinesurya you still need to re-link the linkedlist after deletion. like this
Node Delete(Node head, int position) { if (head == null) return null;
if (position == 0) { head = head.next; } else { Node back = head; for (int i=0;i<position-1;++i) { back = back.next; } back.next = back.next.next; } return head;}
divyanshidm Cool! But I have a question. When return head is actually executed and does it just return all the following elements of element to be deleted?
ishanshekhar0502 Well here's my take to it!
Node* Delete(Node *head, int position) { struct Node *i,*j,*newn; int count=0; if(position==0 &&head->next!=NULL){ j=head; head=head->next; //free(j); } else{ i=head; j=i; while(i->next!=NULL&&count<position){ j=i; i=i->next; count++; } j->next=i->next; free(i); } return(head); }
gg_germain Nice and easy, but prone to reaching overflows for long lists. And if head is null and position ==0, then we try to access null.next, which in most languages leads to an error
ME_170070175 commplete this method Node *prev = NULL; Node *ptr = head;
int pos = 0; if(position==0) { head=head->next; delete (ptr); } else { while(position!=pos) { ++pos; prev=ptr; ptr=ptr->next; } if(ptr!=NULL) { prev->next=ptr->next; delete (ptr); } } return head;}
ardyanfalah Thank you, i just got an idea after looking at ur solution
ankita_r_pawar Glad to know , that my solution helped u
arthurspa Problems seems to be broken with C++.
Node* Delete(Node *head, int position) { if(position == 0){ Node* next = head->next; delete head; return next; } Node* current = head; Node* prev = head; for(int i = 0; i < position; i++){ prev = current; current = current->next; } prev->next = current->next; delete current; return head; }
Output is correct, however it's not breaking lines correctly:
23 13 12 4351
richrabago The challenge is broken becuase of the need for new lines. Does anybody know how to let them know?
aloksingh3007 The support team need to fix this.
er_warahk Problem is currently broken with python2. Unittests are printing the linked list in a single line, but are expecting the output to have line breaks between each value in the diff.
def Delete(head, position): tmp = Node(next_node=head) current = tmp for x in range(position): current = current.next current.next = current.next.next return tmp.next
B150376CS_kaza I don't get my mistake since we are not known with print funtion For given input 4 3 1 2 3 0 3 1 2 3 1 3 1 2 3 2 5 4 3 2 5 1 2
They given that my output is 23 13 12 4351
And expected output is 2 3 1 3 1 2 4 3 5 1
evsuv Testcase is broken!
rinkeshjain15 here is simple Java Solution
Node Delete(Node head, int position) {
int count=0; if(position==0){ return head.next; } if(head==null){ return head; } Node current=head; while(current.next!=null){ if(count==position-1){ Node temp=current.next.next; current.next=temp; break; } current=current.next; count++; } return head; }fordm13 It is simple but I think based on the input you can assume that using position would be enough to handle going past the list. Or something like this.
Node Delete(Node head, int position) { if(position ==0){ return head.next; }else if(head == null){ return head; } Node current = head; int i = 0; while(i++ < (position-1)){ current = current.next; } current.next = current.next.next; return head; }
Shaary I came up with almost identical solution :)
bgandham simpler solution
Node* Delete(Node *head, int position) {
struct Node *current=head; if(position==0) { head=head->next; return head; } while(position>1) { current=current->next; position--; } struct Node *de=current->next; current->next=(current->next)->next; free(de); return head;}
DrivingEngineer Good, but you missed the free in your position is 0 case.
sanketfarande2 My output is right for each test cases but each node must be printed on new line ,how to do that?
My code:
Node* Delete(Node *head, int position) { // Complete this method Node * prev=head; Node *cn =head; int s=0; while(s!=position) { prev=cn; cn=cn->next; s++; }
if(position!=0) { prev->next=cn->next; cn=NULL; } else { head=head->next; } return head;}
bakseongjin Node* Delete(Node *head, int position) { // Complete this method if(position == 0){ head = head->next; return head; } Node *node = new Node; node = head; for(int i=1; i<position-1; i++){ node = node->next; } node->next = node->next->next; return head; }
This is my code, and I think that test sets are broken.
vin_singh Where do you delete the node and free its memory?
Sort 246 Discussions, By:
Please Login in order to post a comment