467,169 Members | 940 Online

# Middle of a singly linked list of unknown length

 Hi! I was wondering, In the first parse of a singly linked list of unknown length, is it possible to know when we are at middle of the linked list? Regards --Himanshu Jun 27 '08 #1
• viewed: 3889
Share:
23 Replies
 In article , Himanshu Chauhan I was wondering, In the first parse of a singly linked list of unknownlength, is it possible to know when we are at middle of the linked list? Obviously not, since nothing would be different if extra elements were added to the end. -- Richard -- In the selection of the two characters immediately succeeding the numeral 9, consideration shall be given to their replacement by the graphics 10 and 11 to facilitate the adoption of the code in the sterling monetary area. (X3.4-1963) Jun 27 '08 #2
 I was wondering, In the first parse of a singly linked list of unknown length, is it possible to know when we are at middle of the linked list? You could do it if you kept track of how many were in the list when you built it. Jun 27 '08 #3
 On Jun 6, 1:48 pm, Himanshu Chauhan
 Himanshu Chauhan
 Himanshu Chauhan wrote: > I was wondering, In the first parse of a singly linked list of unknown length, is it possible to know when we are at middle of the linked list? Yes. Just build the list in two halves, and join them when building is done. The head of the second half will be the midpoint, withing an error of one. -- [mail]: Chuck F (cbfalconer at maineline dot net) [page]: Try the download section. ** Posted from http://www.teranews.com ** Jun 27 '08 #6
 Himanshu Chauhan wrote: > Hi! I was wondering, In the first parse of a singly linked list of unknown length, is it possible to know when we are at middle of the linked list? The me rephrase the problem, and see if you can find a solution: Drive down this road and stop halfway to a destination which I have not yet revealed. -- +-------------------------+--------------------+-----------------------+ | Kenneth J. Brody | www.hvcomputer.com | #include | | kenbrody/at\spamcop.net | www.fptech.com | Jun 27 '08 #7
 "Kenneth Brody" >Hi!I was wondering, In the first parse of a singly linked list of unknownlength, is it possible to know when we are at middle of the linked list? The me rephrase the problem, and see if you can find a solution: Drive down this road and stop halfway to a destination which I have not yet revealed. That's not quite the same. In that case you would not know when you got to the destination so it's unsolveable. A linked list however has a definite end point, assuming it's not circular. Better, 'stop halfway to the end of the road of unknown length'. Easily done by traversing the entire length one and a half times. -- Bartc Jun 27 '08 #8
 CBFalconer I was wondering, In the first parse of a singly linked list ofunknown length, is it possible to know when we are at middle ofthe linked list? Yes. Just build the list in two halves, and join them when building is done. The head of the second half will be the midpoint, withing an error of one. Right, finding a solution is easy if you're allowed to redefine the problem. The problem statement assumed "a singly linked list of unknown length", not two lists of equal length. -- Keith Thompson (The_Other_Keith) ks***@mib.org Nokia "We must do something. This is something. Therefore, we must do this." -- Antony Jay and Jonathan Lynn, "Yes Minister" Jun 27 '08 #9
 On 6 Jun 2008 at 16:36, Keith Thompson wrote: CBFalconer Right, finding a solution is easy if you're allowed to redefine the problem. Vintage CBF. At least two people have already provided a correct solution (i.e. run two pointers through the list, one travelling at half the speed of the other), but several hours later in wades Chuck with something completely wrong-headed. (Still, I suppose at least he tried, albeit unsuccessfully, to answer the damn question for once, instead of telling the OP to get lost and try comp.programming.) Jun 27 '08 #10
 Keith Thompson wrote: CBFalconer Himanshu Chauhan wrote: >>I was wondering, In the first parse of a singly linked list ofunknown length, is it possible to know when we are at middle ofthe linked list? Yes. Just build the list in two halves, and join them whenbuilding is done. The head of the second half will be themidpoint, withing an error of one. Right, finding a solution is easy if you're allowed to redefine the problem. The problem statement assumed "a singly linked list of unknown length", not two lists of equal length. To have the single list, you have to form it, by adding one item at a time. The break into two portions does this. If you don't like having two lists during formation, just have one, and add items alternately before the 'middle' and at the 'end'. -- [mail]: Chuck F (cbfalconer at maineline dot net) [page]: Try the download section. ** Posted from http://www.teranews.com ** Jun 27 '08 #11
 In article , Antoninus Twink At least two people have already provided a correctsolution (i.e. run two pointers through the list, one travelling athalf the speed of the other) That's not a solution to the problem as I interpreted it. It uses one-and-a-half passes over the list, rather than stopping in the middle during the first pass. -- Richard -- In the selection of the two characters immediately succeeding the numeral 9, consideration shall be given to their replacement by the graphics 10 and 11 to facilitate the adoption of the code in the sterling monetary area. (X3.4-1963) Jun 27 '08 #12
 Antoninus Twink wrote: On 6 Jun 2008 at 16:36, Keith Thompson wrote: >CBFalconer Right, finding a solution is easy if you're allowed to redefine theproblem. Vintage CBF. At least two people have already provided a correct solution (i.e. run two pointers through the list, one travelling at half the speed of the other), I think those so-called solutions are ruled out by the O.P.'s requirement to get the answer "in the first parse" over the list, which I read as a garbled form of "in the first pass" over the list. Using two pointers means using one-and-a-half passes. Still, I suppose at least he tried, albeit unsuccessfully, to answer the damn question for once, instead of telling the OP to get lost and try comp.programming.) Right, that was a mistake on his part. Chuck, I hereby chastise you for answering an off-topic question instead of sending the questioner to comp.programming where he belongs and where he'll get better answers. -- Er*********@sun.com Jun 27 '08 #13
 Bartc wrote: > "Kenneth Brody" Hi! I was wondering, In the first parse of a singly linked list of unknown length, is it possible to know when we are at middle of the linked list? The me rephrase the problem, and see if you can find a solution: Drive down this road and stop halfway to a destination which I have not yet revealed. That's not quite the same. In that case you would not know when you got to the destination so it's unsolveable. A linked list however has a definite end point, assuming it's not circular. Perhaps I should have included my implied: "I'll tell you when you get to the end." (Just as a singly-linked list has a "destination not yet revealed" until you reach the end.) Better, 'stop halfway to the end of the road of unknown length'. Same thing. Easily done by traversing the entire length one and a half times. Which doesn't qualify as "first parse['pass'?]" as stated by the OP. -- +-------------------------+--------------------+-----------------------+ | Kenneth J. Brody | www.hvcomputer.com | #include | | kenbrody/at\spamcop.net | www.fptech.com | Jun 27 '08 #14
 On 6 Jun 2008 at 17:55, Eric Sosman wrote: I think those so-called solutions are ruled out by the O.P.'s requirement to get the answer "in the first parse" over the list, which I read as a garbled form of "in the first pass" over the list. Using two pointers means using one-and-a-half passes. [snip] I interpreted the OP's requirement as a garbled form of an old chestnut textbook exercise. > Chuck, I hereby chastise you for answering an off-topic question instead of sending the questioner to comp.programming where he belongs and where he'll get better answers. Even the people in comp.programming aren't able to do the impossible. Jun 27 '08 #15
 CBFalconer CBFalconer >Himanshu Chauhan wrote:I was wondering, In the first parse of a singly linked list ofunknown length, is it possible to know when we are at middle ofthe linked list?Yes. Just build the list in two halves, and join them whenbuilding is done. The head of the second half will be themidpoint, withing an error of one. Right, finding a solution is easy if you're allowed to redefinethe problem.The problem statement assumed "a singly linked list of unknownlength", not two lists of equal length. To have the single list, you have to form it, by adding one item at a time. The break into two portions does this. If you don't like having two lists during formation, just have one, and add items alternately before the 'middle' and at the 'end'. I still say you're changing the requirements. You can also keep track of the number of items in the list as you create it, or you can store the nodes of the linked list in a contiguous array, either of which makes it possible to find the middle without traversing the whole thing. But the problem as stated referred to "a singly linked list of unknown length", presumably one given to you by some outside source. -- Keith Thompson (The_Other_Keith) ks***@mib.org Nokia "We must do something. This is something. Therefore, we must do this." -- Antony Jay and Jonathan Lynn, "Yes Minister" Jun 27 '08 #16
 "Himanshu Chauhan" __________________________________________________ ______________ struct slist { struct slist* next; }; #define CHUNK 32 #define GROWBY 2 static struct slist* slist_get_middle_on_one_iteration( struct slist* _this ) { size_t i = 0; size_t nl = CHUNK; struct slist* nodes = malloc(sizeof(*nodes) * nl); while (_this) { if (i >= nl) { nl *= GROWBY; nodes = realloc(nodes, sizeof(*nodes) * nl); } nodes[i++] = _this; _this = _this->next; } if (i) { _this = nodes[i / 2]; } free(nodes); return _this; } __________________________________________________ ______________ Is that anywhere near what your looking for? Jun 27 '08 #17
 On Jun 6, 1:48*am, Himanshu Chauhan
 "Chris Thomasson" Hi!I was wondering, In the first parse of a singly linked list of unknownlength, is it possible to know when we are at middle of the linked list? Does "first parse" mean 1 pass through the _entire_ list? If so, then I guess you could do something like this: __________________________________________________ ______________ struct slist { struct slist* next; }; #define CHUNK 32 #define GROWBY 2 static struct slist* slist_get_middle_on_one_iteration( struct slist* _this ) { size_t i = 0; size_t nl = CHUNK; struct slist* nodes = malloc(sizeof(*nodes) * nl); ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^ I got the size wrong! Here is correction: struct slist* nodes = malloc(sizeof(nodes) * nl); while (_this) { if (i >= nl) { nl *= GROWBY; nodes = realloc(nodes, sizeof(*nodes) * nl); ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^ Ditto: nodes = realloc(nodes, sizeof(nodes) * nl); Sorry about that. } nodes[i++] = _this; _this = _this->next; } if (i) { _this = nodes[i / 2]; } free(nodes); return _this; } __________________________________________________ ______________ Is that anywhere near what your looking for? Jun 27 '08 #19
 "Chris Thomasson" Hi!I was wondering, In the first parse of a singly linked list of unknownlength, is it possible to know when we are at middle of the linked list? Does "first parse" mean 1 pass through the _entire_ list? If so, then I guess you could do something like this: __________________________________________________ ______________ struct slist { struct slist* next; }; #define CHUNK 32 #define GROWBY 2 static struct slist* slist_get_middle_on_one_iteration( struct slist* _this ) { size_t i = 0; size_t nl = CHUNK; struct slist* nodes = malloc(sizeof(*nodes) * nl); ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^ ARGH! I want an array of slist pointers, NOT slist objects! struct slist** nodes = malloc(sizeof(*nodes) * nl); while (_this) { if (i >= nl) { nl *= GROWBY; nodes = realloc(nodes, sizeof(*nodes) * nl); } nodes[i++] = _this; _this = _this->next; } if (i) { _this = nodes[i / 2]; } free(nodes); return _this; } __________________________________________________ ______________ Is that anywhere near what your looking for? Here is some code which compiles: __________________________________________________ ______________ #include #include #include struct slist { struct slist* next; }; #define CHUNK 32 #define GROWBY 2 static struct slist* slist_get_middle_on_one_iteration( struct slist* _this ) { size_t i = 0; size_t nl = CHUNK; struct slist** nodes = malloc(sizeof(*nodes) * nl); if (nodes) { while (_this) { if (i >= nl) { struct slist** new_nodes; nl *= GROWBY; new_nodes = realloc(nodes, sizeof(*new_nodes) * nl); if (! new_nodes) { free(nodes); return NULL; } nodes = new_nodes; } nodes[i++] = _this; _this = _this->next; } if (i) { _this = nodes[i / 2]; } free(nodes); return _this; } return NULL; } int main(void) { struct slist nodes[5]; struct slist* middle; nodes[0].next = nodes + 1; nodes[1].next = nodes + 2; nodes[2].next = nodes + 3; nodes[3].next = nodes + 4; nodes[4].next = NULL; middle = slist_get_middle_on_one_iteration(nodes); assert(middle == nodes + 2); puts("\n\npress
 CBFalconer
 "Chris Thomasson" "Himanshu Chauhan" >Hi!I was wondering, In the first parse of a singly linked list of unknownlength, is it possible to know when we are at middle of the linked list? Does "first parse" mean 1 pass through the _entire_ list? If so, then Iguess you could do something like this: [...] Here is some code which compiles: __________________________________________________ ______________ #include #include #include struct slist { struct slist* next; }; #define CHUNK 32 #define GROWBY 2 static struct slist* slist_get_middle_on_one_iteration( struct slist* _this ) { size_t i = 0; size_t nl = CHUNK; struct slist** nodes = malloc(sizeof(*nodes) * nl); if (nodes) { while (_this) { if (i >= nl) { struct slist** new_nodes; nl *= GROWBY; new_nodes = realloc(nodes, sizeof(*new_nodes) * nl); if (! new_nodes) { free(nodes); return NULL; } nodes = new_nodes; } nodes[i++] = _this; _this = _this->next; } if (i) { _this = nodes[i / 2]; } free(nodes); return _this; } return NULL; } int main(void) { struct slist nodes[5]; struct slist* middle; nodes[0].next = nodes + 1; nodes[1].next = nodes + 2; nodes[2].next = nodes + 3; nodes[3].next = nodes + 4; nodes[4].next = NULL; middle = slist_get_middle_on_one_iteration(nodes); assert(middle == nodes + 2); puts("\n\npress
 On Tue, 10 Jun 2008 22:53:03 -0700, "Chris Thomasson" wrote: >Humm... I think I just did somebody's homework! Probably. I didn't look at your code, but it looks more complex than what I was thinking: Two pointers start at the head. Each time you move one of the two, more the other one just one. -- #include _ Kevin D Quitt USA 91387-4454 96.37% of all statistics are made up Jun 27 '08 #23
 "Kevin D. Quitt" wrote: >>Humm... I think I just did somebody's homework! Probably. I didn't look at your code, but it looks more complex than what I was thinking: Two pointers start at the head. Each time you move one of the two, more the other one just one. You mean something like: A->B->C->D->E->NULL / The middle is node C Iteration ____________________ 1: cur = A; 2: middle = A; 3: cur = B; 4: cur = C; 5: middle = B; 6: cur = D; 7: cur = E; 8: middle = C; /*** GOT IT! ***/ That works but I am not sure it "strictly" adheres to the rules as-is. I guess one could argue that your actually making one-and-a-half parses; not just one. The `cur' pointer constitutes a full parse, while the `middle' pointer represents half a parse. See, it took 8 links to parse a list of 5 nodes. The solution I hacked together can solve this problem using only 5 links. This is how I understand the rules. Perhaps I am missing something here... Any thoughts? Jun 27 '08 #24

### This discussion thread is closed

Replies have been disabled for this discussion.