j****9
发帖数: 2295 | 1 一次遍历找到单链表倒数第m个元素。
一道老题。
网上有code。看起来没什么问题。但也有人说这个不是一次遍历。求一次遍历的正解代码。
只是对于test case 怎么写不太清楚。
struct iNode {
int value;
iNode * next;
};
iNode * getresult(iNode * head,int n)
{
iNode *pfirst;
iNode *psecond;
pfirst=head;
int counter;
for(counter=0;counter
pfirst=pfirst->next;
}
psecond=head;
while(pfirst!=NULL) {
pfirst=pfirst->next;
psecond=psecond->next;
}
return psecond;
} | j****9
发帖数: 2295 | 2 如果这个算是两次遍历的话。
谁能给个一次遍历的正解。急用。谢谢。 | s***e
发帖数: 122 | 3 这个就是一次遍历，但是有一些bug, 没有考虑n<0以及链表长度小于n+1的情况。下面
是一些修改以及测试用例。
#include
struct iNode {
int value;
iNode * next;
iNode() { value = 0; next = NULL; }
iNode(int v) : value(v) { next = NULL; }
iNode(int v, iNode* nx) : value(v), next(nx) {}
};
iNode * getNthLastNode(iNode * head, int n) {
if (head == NULL || n < 0) return NULL;
iNode* pfirst = head;
for (int counter = 0; counter < n; counter++) {
if (pfirst->next != NULL)
pfirst = pfirst->next;
【在 j****9 的大作中提到】
: 如果这个算是两次遍历的话。
: 谁能给个一次遍历的正解。急用。谢谢。
| j****9
发帖数: 2295 | 4 测试用例没太看明白。
其实原题只问了倒数第5个，所以我写个general函数时没考虑n为负数的情况。
iNode() { value = 0; next = NULL; }
iNode(int v) : value(v) { next = NULL; }
iNode(int v, iNode* nx) : value(v), next(nx) {}
这三行必要么？ | j****9
发帖数: 2295 | 5 我是用文字表达test cases的。
Empty Linked list {}, expected output null
Linked list of one element {1}, expected output null
Linked list of five elements {1, 2, 3, 4, 5}, expected output 1
Linked list of more than five elements {1, 2, 3, 4, 5, 6}, expected output 2
需要写成程序? 能帮写一个么？ | s***e
发帖数: 122 | 6 如果是应聘测试的话，那就要更加细心一点了，比如还要排除head == NULL的情况。
那三行是为了写代码简单一点。否则你new了一个iNode,你还要设置value和next。前提
是你是在写C++代码，如果是C代码那就只好麻烦一点了。
【在 j****9 的大作中提到】
: 测试用例没太看明白。
: 其实原题只问了倒数第5个，所以我写个general函数时没考虑n为负数的情况。
: iNode() { value = 0; next = NULL; }
: iNode(int v) : value(v) { next = NULL; }
: iNode(int v, iNode* nx) : value(v), next(nx) {}
: 这三行必要么？
| s***e
发帖数: 122 | 7 。。。希望你不是应聘开发的职位，呵呵
// 从数组构建链表的函数
iNode * buildLinkList(int a[], int n) {
if (a == NULL || n <= 0) return NULL;
iNode* head = new iNode(a[0]);
iNode* tail = head;
for (int i = 1; i < n; ++i) {
tail->next = new iNode(a[i]);
tail = tail->next;
}
return head;
}
// 释放链表内存的函数
void destroyLinkList(iNode* head) {
while (head != NULL) {
iNode* tmp = head->next;
delete head;
head = tmp;
}
}
// 打印链表
void printLinkList(iNode* head) {
if
【在 j****9 的大作中提到】
: 我是用文字表达test cases的。
: Empty Linked list {}, expected output null
: Linked list of one element {1}, expected output null
: Linked list of five elements {1, 2, 3, 4, 5}, expected output 1
: Linked list of more than five elements {1, 2, 3, 4, 5, 6}, expected output 2
: 需要写成程序? 能帮写一个么？
| c******a
发帖数: 18 | 8 递归？或者用stack？
代码。
【在 j****9 的大作中提到】
: 一次遍历找到单链表倒数第m个元素。
: 一道老题。
: 网上有code。看起来没什么问题。但也有人说这个不是一次遍历。求一次遍历的正解代码。
: 只是对于test case 怎么写不太清楚。
: struct iNode {
: int value;
: iNode * next;
: };
: iNode * getresult(iNode * head,int n)
: {
|
|
|
