# Get Node Value

# Get Node Value

salcio + 61 comments Hi,

I think I found quite nice soution - no recursion, no arrays. We iterate only once through whole list.

`int GetNode(Node *head,int positionFromTail) { int index = 0; Node* current = head; Node* result = head; while(current!=NULL) { current=current->next; if (index++>positionFromTail) { result=result->next; } } return result->data; }`

talluri + 5 comments can you explain why your code works ??

salcio + 13 comments yeah. so we have two pointers. one is a iteration pointer and the other will be behind it by requested number of elements. so for example lets say we need to get value of 3rd element from tail. we start incrementing second pointer after 3rd element alongside with iteration pointer. When iteration pointer gets to the end(tail) second pointer is going to be pointing to 3rd element from it. which is our answer. hope that helps.

harrish96 + 1 comment i wasnt able to understand some of your code, but it gave me an idea which worked , so thanks.

changhaoran144 + 3 comments Think about two cars: C(current) and R(result). They have the same speed and C is in fromt of R. The distance between them is the value of positionFromTail. So when C arrive at the ending point, where is R? Note that their distance is "positionFromTail", the position of R is the position from tail.

callniladri_pro + 1 comment Nice explanation.

shuklaaakash75 + 0 comments well done

Sufiyan + 0 comments Amazing! I did not think about it in this way. This is a good solution and easy to understand. Thanks.

israa_samkari + 0 comments How did you become like that? i mean how you get solve it like this??! this is crazy man, i wanna some day become like you :)

tvthanh95 + 0 comments thanks.

ErikTest + 0 comments Clever!

tanmayub + 0 comments Awesome..!! Thanks..!! :)

sandymark0346 + 0 comments I know this is a bit odd, but I understand what your code is doing, but not why it works?

mudit_goel1421 + 1 comment An intuitive explanation would be: just imagine the two pointers, current and result as sprinters. If each node represented a milestone and let it takes for them to move between consecutive stones 1 second, thus both have equal speeds(imagine index represents time passage starting from index = 0 when refree fired his gun.). Hence in each iteration, the two would move from starting point to next adjacent milestone. When current reaches the last milestone, result must be at positionfromtail milestone and because both move with equal speeds it means that current must have a headstart of positionfromtail seconds over result. Clearly, result must start moving (result=result->next) only after time greater than positionfromtail (index++>positionfromtail).

DarshakMehta + 1 comment I feel like one is exactly after the other i.e. gap between both are always 1. Or cant really understand how it worked. Really... sorry if I bothering you, but havent understood how it works. Help me please...

geuis + 3 comments Ok I was confused by this too and literally when I woke up this morning I understood how it works. Here is a version of the answer written in Python that should be easier to understand.

def GetNode(head, position): trailingNode = head len = 0 while (head): if (len > position): trailingNode = trailingNode.next len += 1 head = head.next return trailingNode.data

The mental image that came to me is dragging a rope of a certain length. (Remember, this was a dream.)

In a simple example, suppose we have the list

`1 2 3 4 5`

and we want to get position 3 from the end.As we advance to each new node, we incremenent the

`len`

value.When

`len`

is finally greater than the`position`

value, that's the length of our rope. In this case, the length of the rope is 3 (3 nodes).As

`head`

keeps advancing through the list, we start "dragging the rope" by advancing`trailingNode`

through the list behind`head`

.Now that

`len`

is greater than the position, we start advancing`trailingNode`

through the same list, but at 3 node positions behind`head`

.Finally, when

`head`

reaches the end of the list`trailingNode`

is now at the position of list length minus position.1 2 3 4 5 < head ^ trailingNode

subbuvenk + 0 comments Nice explanation :D

RJ_dot_PY + 1 comment Awesome!!

keta_thatte + 0 comments easy and awsome!

ltumuhairwe + 0 comments [deleted]

AMITAGA + 1 comment Hi,

Although this is correct solution but this given running time complexity is O(n^2)

Better Solution: Algorithm 1.find the length of the linkedList by iteraing it. Let length be L. 2.Nth node from the last of the linkedList is L-(N+1) node from the head.

Time Complexity O(2n) ~ O(n)

andrewseaman35 + 1 comment Salcio's solution will only have a complexity of O(n). It is actually quicker than your solution, which will iterate through the list twice. Instead, Salcio's will only iterate through it once.

The while loop will run

`current`

through the entire list and stop once it has reached the end.whoiscris + 4 comments Ok, kids, let's learn some Complexity 101!

**both algorithms are linear**, i.e. O(n).Even the constants in their linearity are the same, because

**both iterate through the same number of elements**!

Still confused ?

denizsayin + 0 comments You are actually right! The two algorithms are almost the same. The only difference is that in salcio's algorithm the pointer which is behind is advanced at the same time as the main pointer, while in AMITAGA's solution the same is done AFTER that. I had not noticed that. Mind = Blown... Thank you!

Piyushpky + 0 comments Haha Mr.Overconfident! :D Both algos are linear but one is O(2n) and the other is of O(N).Go do work on your basics. KID.

Yeetesh + 0 comments I think salcio's solution is better as it is O(n) and not O(2n). Basic step here is checking the if condition and not the statement inside the if statement.

tpaktopa + 1 comment Loop is much slower then Value assigning. Debug with Disassemmbler on, and see the difference. Disassemble it, and see, that :

- Value assiging is 1 or 3 CPU cycles ( depends, is variable in CPU register or in memory. Local variables are usually in CPU register, and it tooks 1 CPU cycle to assign)
Loop is 6 to 20+ CPU cycles - depnds, is it simple while, which actually internal is IF and JUMP operands, or it's a FOR, or even slower FOREACH

So,

while(condition) { a = b; if(condition) c = b; }

is much, much faster then

while(condition) { a = b; index++; } while(index-- > 0) c = b;

Still, there is one small issue with SALCIO's code.

if (index++ > positionFromTail) result=result->next;

index++ (increment) is unneeded, after once index is bigger then positionFromTail. Though increment with ++ is only 1 CPU cycle ( INC operator), i with do it like:

if (index > positionFromTail) result=result->next; else index++;

hwfbcisod + 0 comments I feel like your comment is underappreciated.

SohanReddy + 0 comments Clear and clever!

karanth + 0 comments Brilliant! :)

s_sagarsen1 + 0 comments fantastic

jimit_silenthill + 0 comments Excellent!! approach which is efficient as no need for recursion or first iterate till end to get count of nodes.

aktersuriya + 0 comments Nice logic !!

anil_alanka + 1 comment Simple and Clever!!

tanmayub + 0 comments [deleted]

etayluz + 13 comments Simple and elegant answer!

Here's a recursive solution just for giggles:

`int GetNode(Node *head, int positionFromTail) { int data; if (head->next == NULL) { // store the position in the data variable data = head->data; head->data = 0; // return the data return data; } data = GetNode(head->next, positionFromTail); if (head->next->data == positionFromTail) { head->data = head->next->data; return data; } else { data = head->data; head->data = head->next->data + 1; return data; } }`

sandeepsr21 + 0 comments I Have seen most of your solutions. They are just simple and elegant.

DHARIK + 1 comment if (head->next->data == positionFromTail) In this loop how the data of the node comparing with the index;Could u explain me;

kedar_nadkarny + 1 comment I know right! wth?

EasyPancakes + 0 comments [deleted]

mukesh9871 + 1 comment Could you/any one please explain. How it is working. I am not able to decipher it.

mukesh9871 + 0 comments I deciphered it. Thanks for it amazing solution.

vsvamsi + 0 comments Recursions are misreably hard...need to practise more...nevertheless excellent solution

abhinav_90 + 1 comment i was thinking if i can solve it through recursion and ended up concluding may be i can't because i have to somehow need a variable which holds positionfromlast value of each node and i can't embbed that info in return value since return has diff purpose in this question.

I actually giggled when i saw that you destroyed who list to return just one value :D

tanmay777 + 0 comments I was actually stuck at the same situation of yours for an hour xD. I wonder how this problem can be done recursively without destroying the linked list. I know its possible, as any program which can be written iteratively can be also written recursively and vice versa.

peterkirby + 1 comment A different recursive solution. Uses pass-by-reference.

`int GetNode(Node *head, int & positionFromTail) { if (head == NULL) return 0; int answer = GetNode(head->next, positionFromTail); if (positionFromTail == -1) { return answer; } else { --positionFromTail; return head->data; } }`

vishwasjha17 + 1 comment hey!why did you pass positionFromTail as a refrence

zzmmss + 0 comments because u won't know where is the tail until u iterate a whole LinkedList. if we have a length 5 list and want to get positionFromTail 2, we will go this way: 4 3 2 1 0 1 2

gundamunit + 0 comments If you always have to corrupt the data you stored in your list to get the data stored in some position, I guess it's a on time use method.

hockeyshark315 + 2 comments ### How about this recursive solution?

int length,answer; int GetNode(Node head,int n) { genNodeHelper(head,n,0); return answer; } void genNodeHelper(Node head, int n, int index){ if(head == null) length = index-1; else genNodeHelper(head.next, n, index+1); if(length - n == index) answer = head.data; }

GIWMCoder + 0 comments @hockeyshark315, excellent recursive solution! Surprised that this answer hadn't received any upvote(s).

tpaktopa + 0 comments Recursive call is much much slower, then simple while cycle. Still, your sollution is OK.

srjkmr619 + 1 comment Your code gives the right answer, but it changes the data of every nodes in the lists.What good is this function if i cannot preserve my original linked list?

vijay96 + 2 comments Look at the code carefully Mr.Suraj kumar,I have simply traversed the list..

int GetNode(Node *head,int positionFromTail)

{

`int index=0; struct Node *temp=head,*result=head; while(temp!=NULL){ temp=temp->next; if(index++ > positionFromTail) result=result->next; } return result->data;`

}

srjkmr619 + 0 comments Man...i have referred to etayluz's code,not yours.

srjkmr619 + 0 comments [deleted]cray1 + 0 comments This is destructive to the original list however. It "solves the problem", but you better not need that list afterwards.

sbsatter + 0 comments The above code segment will modify the original List in the memory, won't it?

bhuvnesh_kumar + 0 comments @etayluz i can't understand this solution could you please explain.

mudit_goel1421 + 0 comments [deleted]hjkajh + 0 comments That's mean, the result pointer is later than current pointer positionFromTail positions. When current is the tail, the result will be positionFromTail positions from tail!!!

aqueiroz + 0 comments The way you solved this the best one in my opinion. Congratulations!!!

CVitthal + 0 comments Nice

RobotMa + 0 comments Really nice logic!

sheeze_pk + 0 comments nice logic :)

freddGO + 0 comments Clever

cansay + 0 comments Excellent work!!

jonmcclung + 0 comments very clever!

_kuldeep_ + 0 comments Elegant solution... Bravo

bks4line + 0 comments Brilliant solution!

alejandro33 + 0 comments Really nice congrats!!

jja23 + 0 comments How did you come up with this? Beautiful.

Minyi + 0 comments Very smart solution !

c650Alpha + 0 comments very clever. I adapted this and it all worked out!

sandeepsr21 + 0 comments Awesome.

maximshen + 0 comments 1) Similar idea of using two points to detect whether there is any cycle or not.

2) Also, pay attention to the differece between C++ and Java about their operator priority. C++ (index++>positionFromTail) equals to (++index>positionFromTail) !

bastianl7 + 1 comment Nice Solution. Here is the same idea in python:

def GetNode(head, position): tracked = head while position > 0: head = head.next position -= 1 while head.next: head = head.next tracked = tracked.next return tracked.data

Vinprogress + 0 comments wow!!

kvpratama + 2 comments Brilliant!!

Here is my code in java based on your algorithm.

`int GetNode(Node head, int n) { Node pointer = head; int pointerPosition = 0; while (head.next != null){ head = head.next; if (pointerPosition < n){ pointerPosition++; }else { pointer = pointer.next; } } return pointer.data; }`

mike800 + 0 comments That's brilliant, salcio! I'm surprised their test case allow passing with double traversal.

arohwedd + 0 comments Ahhh this is great. Smart person!

arjun1321 + 0 comments very clever solutions

ved57 + 0 comments I hate to see solutions in the Discussions page. But this one is an exception. Clever and simple. Persons who get the solution correct at first go and miss this post are going to be unlucky...

doanhuunoi + 0 comments awesome, you're so smart!

vijay96 + 0 comments nice idea...

jogi9045 + 1 comment void printNthFromLast(struct node* head, int n) { static int i = 0; if (head == NULL) return; printNthFromLast(head->next, n); if (++i == n) printf("%d", head->data); }

rcashie + 0 comments Very nice, doing (n - positionFromTail) iterations from the head by ignoring the first (positionFromTail) when counting all (n).

navrattanocp + 0 comments there is no need to declare current : Java Solution :

int GetNode(Node head,int n) { Node result = head; int i = 0; while(head != null) { head = head.next; if(i++ > n) { result = result.next; } } return result.data;

}

kev01 + 2 comments Salcio, your solution is excellent, but you can simplify the code even further by not maintaining a separate "current" pointer.

int GetNode(Node *head,int positionFromTail) { Node* tortoise = head; int index = 0; while (head->next) { head = head->next; if (++index > positionFromTail) { tortoise = tortoise->next; } } return tortoise->data; }

simran250122 + 0 comments Awesome :)

nike3801 + 0 comments Awesome!! I really am implressed by your logic.

nm1511 + 0 comments oh dam son

k_shreyans1 + 0 comments really good one

themast3r + 0 comments Smart, heck smart!

samuu + 0 comments Salute to this solution!!! awesome!!

meecheck + 0 comments [deleted]jsu317 + 0 comments Beautiful solution

hackersundar + 1 comment Nice approach. But, we dont need current pointer here. This solution works without that.

Python code (same approach)def GetNode(head, position): index = 0 result = head while(head.next != None): head = head.next index += 1 if(index > position): result = result.next return result.data

jae_duk_seo + 0 comments this is really good solution.

parisgeller + 0 comments When you think about it, its the same thing as explained in the editorial combined inside one loop.

bsandeepgupta + 0 comments Fantastic :)

raj_yadav29oct + 0 comments super

harpz_ + 0 comments Awesome..

zjuPeco + 0 comments it's really an amazing way to solve this problem!

ajinkya_ghonge + 1 comment Awesome logic

shuklaaakash75 + 0 comments thanx

holy_monk + 0 comments Kudos Dude! smart thinking!

Vin436 + 0 comments simple java solution based on this algorithm

int GetNode(Node head,int n) { // This is a "method-only" submission. // You only need to complete this method. Node curr = head; for(int i = 0; i<n;i++){ head = head.next; } while(head.next!=null){ head=head.next; curr=curr.next; } return curr.data; }

ldai100 + 0 comments ingenious.

telma92 + 0 comments kudos! very clever solution.

zzmmss + 0 comments INCREDIBLE!!

daimengchen + 0 comments shorter

int GetNode(Node *head,int positionFromTail) { Node *p = head; while(head) { if(positionFromTail < 0) p = p->next; positionFromTail--; head = head->next; } return p->data; }

tanmay777 + 0 comments How are you people so smart -.-

SanthoshGotur + 0 comments great solution

24_riddhi + 0 comments Awesome man!

fernando_luz + 0 comments Great explanation. I rewrite the idea in the following way

int GetNode(Node *head,int positionFromTail) { // walks in the liked list Node *iter = head; for (int i=0; i <= positionFromTail; ++i){ iter = iter->next; } Node *result=head; while(iter != NULL){ iter = iter->next; result = result->next; } return result->data; }

ME_170070246 + 0 comments Thank you for the code it's really a nice one.

dhrjsoni01 + 0 comments superb logic .

khyati398 + 0 comments Incredible,it's very smart solution i just want to ask you that how did you think of this solution ,can you tell me the strategy behind this, if you could than it would be really kind of you :) :) :)

xdavidliu + 0 comments note that this is completely equivalent to iterating twice through the list with a single pointer, since we are iterating two pointers.

shivamfromkanpur + 0 comments [deleted]perfectcodder + 0 comments Nice idea !!

sharonalexander1 + 0 comments Amazing solution! I would have never thought like this.

RodneyShag + 1 comment ### O(1) space complexity Java Iterative solution.

From my HackerRank solutions.

I use the "runner" technique. We make a

*runner*pointer move*k*elements into the list. Then we create a*curr*pointer. We move both pointers 1 step at a time until*runner*is at the end. When this happens,*curr*will be at the kth to last element.Runtime: O(n)

Space Complexity: O(1)int GetNode(Node head, int k) { Node curr = head; Node runner = head; /* Move runner into the list by k elements */ for (int i = 0; i < k; i++) { runner = runner.next; } /* Move both pointers */ while (runner.next != null) { curr = curr.next; runner = runner.next; } return curr.data; }

Let me know if you have any questions.

sandy00 + 1 comment But we start from tail position

i am failed to understand this.. Please explain

RodneyShag + 0 comments Hi. We start from the head position, not the tail. I basically make 1 pointer walk

*k*elements into the list. At the beginning of the*while*loop, we have 1 pointer at the head of the list and 1 pointer*k*elements into the list. Now, we move both pointers 1 step at a time. When the*runner*pointer (the pointer that was inside the list) reaches the end of the list, that means we have our other pointer reach the kth-to-last element.If this still doesn't make sense, I recommend drawing a linked list with paper and pencil and walking through the code with it to better visualize it.

onuremreerol + 2 comments Here is another clean and tidy solution in java. If you have any question, feel free to ask.

int GetNode(Node head,int n) { Node temp = head; for (int i = 0; head.next != null; i++) { head = head.next; if ( i >= n) temp = temp.next; } return temp.data; }

bakaitBaalak + 0 comments Awesome and simple logic.

sirikisaikiran + 1 comment Can you tell me what i>=n does in your if statement.

onuremreerol + 1 comment It counts the position. We know that we need nth position from the tail. When we reach the tail we temp must be the tail-nth element. So we pass first nth element with this comparison so that temp always goes nth element behind current position. In these code head behaves as current.

sirikisaikiran + 0 comments Thanks a lot

badsanjay + 0 comments simple answer :)

int GetNode(Node head,int n) {

`Node cu = head ; Node pu = head; int p =0; while (cu != null){ cu = cu.next; p++; } while (p-n>1){ pu = pu.next; p--; } return pu.data ;`

}

__spartax + 2 comments hii friends this is my solution

def GetNode(head, position): stk = [] t = head while t: stk = [t.data] + stk t = t.next return stk[position]

haotie + 0 comments a new different idea!

bastianl7 + 1 comment instead of prepending to the array, you can also do this:

def GetNode(head, position): out = [] while head: out.append(head.data) head = head.next return out[-(position + 1)]

bastianl7 + 1 comment yes although prepends to lists can be expensive! See here: http://stackoverflow.com/a/7777034

__spartax + 0 comments thanks bro

tbird234 + 1 comment My solution: Iterates through list twice. Solution below is better :) int GetNode(Node head,int n) { // This is a "method-only" submission. // You only need to complete this method. Node currentNode = head; int index = 0; while (currentNode.next != null){ currentNode = currentNode.next; index ++; } currentNode = head; for(int i = 0; i <index-n; i++){ currentNode = currentNode.next; } return currentNode.data; }

shuklayash + 0 comments int getNode( SinglyLinkedListNode * head , int positionFromTail) {

`SinglyLinkedListNode * cur = head; SinglyLinkedListNode *prev =head; while(positionFromTail){ cur=cur->next; positionFromTail--; } while(cur!=NULL){ prev=prev->next; cur=cur->next; } return prev->data;`

}

yaohui_zeng + 0 comments Here is my py3 solution with two pointers: 'slow' and 'fast' with distance being 'position'. We then move the two simultaneously until 'fast' reaches the tail node. Then 'slow' points to the node needed.

def GetNode(head, position): if head == None: return None slow, fast = head, head i = 0 while i < position: fast = fast.next i += 1 while fast.next: fast = fast.next slow = slow.next return slow.data

sid001 + 0 comments **My Java Solution**int GetNode(Node head,int n) { Node curr1 = head; int count = 0; //First count number of elements in linkedlist while(curr1.next != null) { curr1 = curr1.next; count++; } //calculate position from beginning int new_pos = count - n; //Traverse LL till reach the node while(new_pos != 0) { head = head.next; new_pos--; } return head.data; }

AkeemKing + 1 comment Here's a simple solution in Go, for some reason I'm receiving a runtime error for test case #4 but when I used the custom testcase, I received the correct output but it works for every other case and should theoretically work for #4 as well.

func getNode(head *SinglyLinkedListNode, positionFromTail int32) int32 { if head.next == nil || head == nil { return head.data } var nodes []SinglyLinkedListNode for head.next != nil { nodes = append(nodes, *head) head = head.next } length := int32(len(nodes)) return nodes[length-positionFromTail].data }

robotoucan + 0 comments I had a similar issue with testcase #4 with different code. Looks like a problem with the answer

kakyoin01 + 0 comments Straightforward, somewhat efficient iterative solution in JavaScript using an array as a stack:

function getNodeValue(head, position) { var stack = []; var curNode = head; while(curNode) { stack.push(curNode.data); curNode = curNode.next; } while(position) { stack.pop(); position--; } return stack.pop(); }

Sort 337 Discussions, By:

Please Login in order to post a comment