z**********8
发帖数: 229 | 1 2.2 Implement an algorithm to find the nth to last element of a singly
linked list.
这题我的直觉就是两个指针然后保证两者的距离为n，跟它给出的标准解法一样。但是
他有这么一段话：
“Note: This problem screams recursion, but we’ll do it a different way
because it’s trickier. In a question like this, expect follow up questions
about the advantages of recursion vs iteration.”
实在想不出recursion的解法，可以求达人解释一下么？（如果用两个指针的话应该空
间复杂度是O（1）时间是O（n），n是链表长度。用递归可以做的更好么？advantage在
哪里呢？） |
p*****2
发帖数: 21240 | 2 递归的话可以返回next的位置。
最后一个元素返回1,你知道你next的位置，就知道自己的位置了。 |
z****h
发帖数: 164 | |
p*****2
发帖数: 21240 | 4 比如 int check(Node* node,k)
{
if(node==null)
return 0;
int c=1+check(node.next);
if(c==k)
print()
} |
p*****o
发帖数: 1285 | 5 Node* get_back(Node *head, int n){
static int ct;
if (head->next == NULL) {
ct = 0;
return head;
}
Node* res = get_back(head->next, n);
++ct;
if (ct >= n) return res;
else return head;
}
没有检查n是否超过链表尺寸。似乎也是空间O(1),时间O(n)。
questions
【在 z**********8 的大作中提到】
: 2.2 Implement an algorithm to find the nth to last element of a singly
: linked list.
: 这题我的直觉就是两个指针然后保证两者的距离为n，跟它给出的标准解法一样。但是
: 他有这么一段话：
: “Note: This problem screams recursion, but we’ll do it a different way
: because it’s trickier. In a question like this, expect follow up questions
: about the advantages of recursion vs iteration.”
: 实在想不出recursion的解法，可以求达人解释一下么？（如果用两个指针的话应该空
: 间复杂度是O（1）时间是O（n），n是链表长度。用递归可以做的更好么？advantage在
: 哪里呢？）
|
z**********8
发帖数: 229 | 6 谢谢，总觉得用递归不是很straightforward。。。还不如用两个指针。。
【在 p*****2 的大作中提到】
: 比如 int check(Node* node,k)
: {
: if(node==null)
: return 0;
:
: int c=1+check(node.next);
: if(c==k)
: print()
: }
|
z**********8
发帖数: 229 | 7 谢谢，总觉得用递归不是很straightforward。。。还不如用两个指针。。
【在 p*****o 的大作中提到】
: Node* get_back(Node *head, int n){
: static int ct;
: if (head->next == NULL) {
: ct = 0;
: return head;
: }
: Node* res = get_back(head->next, n);
: ++ct;
: if (ct >= n) return res;
: else return head;
|
z**********8
发帖数: 229 | 8 问下：
Node* res = get_back(head->next, n);应该写成：
Node* res = get_back(&（（*head）->next）, n);吧？
【在 p*****o 的大作中提到】
: Node* get_back(Node *head, int n){
: static int ct;
: if (head->next == NULL) {
: ct = 0;
: return head;
: }
: Node* res = get_back(head->next, n);
: ++ct;
: if (ct >= n) return res;
: else return head;
|
p*****2
发帖数: 21240 | 9
递归写起来容易。
【在 z**********8 的大作中提到】
: 谢谢，总觉得用递归不是很straightforward。。。还不如用两个指针。。
|
l*****y
发帖数: 90 | 10 The recursive method could be very similar to the iterative approach:
node* findNtolast(node* head, int n){
for (node*tmp = head, int i=0; inext; tmp=tmp->next){}
recurs(head, tmp);
}
node* recurs(node* head, node* cur){
if (!cur->next)
return head;
else
return rev(head->next, cur->next);
} |
