StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
17821257
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
8
CommunityOwnedDate
CreationDate
2013-07-23T21:17:02.610
FavoriteCount
0
LastActivityDate
2013-07-24T22:42:32.407
LastEditDate
2013-07-24T22:42:32.407
LastEditorUserId
315052
OwnerUserId
315052
ParentId
17820956
PostTypeId
2
Score
4
ViewCount
0
LastEditorDisplayName
text
Body
This problem is not much different from any other reversal problem. One solution is to walk the list, and place each data item into an array. Then, walk the list again, but start at the end of the array, and you overwrite the list data with the values from the array in reverse order. <pre><code>for (n in list) arr[i++] = n->data for (n in list) n->data = arr[--i] </code></pre> If you are not allowed to store anything, then recursion is also out, since it acts as an auxiliary array to store your reversed list. Then a silly solution would be to implement a random access interface to the list: <pre><code>Node * nth_list_item (Node *list, int n); </code></pre> Which returns the <code>n</code>th item of the list. Then, you reverse the list with this interface that lets access it like an array (with a time penalty of course). The reversal no longer takes O(n) time, but is now O(n2). <hr> If recursion is okay, then to satisfy the spirit of the "without storing elements" requirement, you need to walk the list recursively, and then reverse the list as you unwind. This can be accomplished by allowing another parameter to the recursive call to provide the pointer needed to walk through the beginning the list as the recursive calls are unwinding from the end. This implementation uses no extra local variables per recursive call, only the variables provided in the parameters. <pre><code>void swap_left (node *a, node *b, int tmp) { a->data = b->data; b->data = tmp; } void reverse_recursively (node *cur, node **tail) { if (cur) { reverse_recursively(cur->next, tail); if (*tail) { swap_left(cur, *tail, cur->data); if (cur != *tail) *tail = (*tail)->next; if (cur == *tail) *tail = 0; } } } void reverse (node *list) { reverse_recursively(list, &list); } </code></pre> <hr> If we are allowed to encroach upon the spirit of the "without storing elements" requirement when using recursion, then there is a more straight forward (but more space hungry) solution. Basically, a copy of the reversed linked list can be created while recursively traversing it. When the end of it is reached, the list can be traversed again, copying in the elements from the reversed copy. <pre><code>#define make_node(n, d) (node){ n, d } void reverse_recursively (node *list, node *cur, node copy) { if (!cur) { for (cur = &copy; cur; cur = cur->next, list = list->next) { list->data = cur->data; } return; } reverse_recursively(list, cur->next, make_node(&copy, cur->data)); } void reverse (node *list) { if (list == 0) return; reverse_recursively(list, list->next, make_node(0, list->data)); } </code></pre>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POReversing a singly linked list without using any pointers
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USjxh
UserOwnerUserId
1. USjxh
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POReversing a singly linked list without using any pointers
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.