C语言 从最后一个链表中获取第n个

Question

我所做的是，首先我颠倒链表，然后实际上我试图得到一个节点的第n个值。问题是，该函数在反转链表后没有做任何事情，并且由于某种原因没有给出错误。

下面是我的代码:

#include<stdlib.h>
#include<assert.h>
// 1. Create a linked list first
struct Node {
int data;
struct Node* next;
};
// 2. Create traversal function for linked list
void linkedListTraversal(struct Node* ptr) {
while (ptr != NULL) {
printf("%dn", ptr->data);
ptr = ptr->next;
}
}
// 3. Write a function to get the node value from the tail of the linked list
int getNode(struct Node* head, int positionFromTail) {
int value;
struct Node* prevNode = NULL;
struct Node* currNode = head;
struct Node* nextNode;
while (currNode != NULL) {
nextNode = currNode->next;
currNode->next = prevNode;
prevNode = currNode;
currNode = nextNode;
}
head = prevNode;
struct Node* ptr = head;
int count = 0;
while (ptr != NULL) {
if (count == positionFromTail) {
return (ptr->data);
count = count + 1;
ptr = ptr->next;
}
}
assert(0);
}
int main() {
struct Node* head;
struct Node* second;
struct Node* third;
struct Node* fourth;
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
fourth = (struct Node*)malloc(sizeof(struct Node));
head->data = 3;
head->next = second;
second->data = 2;
second->next = third;
third->data = 1;
third->next = fourth;
fourth->data = 0;
fourth->next = NULL;
linkedListTraversal(head);
printf("The value of the node is %d", getNode(head, 2));
}

这是我的输出，如有任何帮助，我将不胜感激。

3
2
1
0

Answer 1

可以创建一个无限循环，因为只有当循环中if语句的条件为true时，指针ptr才会被更改

while (ptr!=NULL)
{
if (count == positionFromTail)
{
return (ptr->data);
count = count + 1;
ptr = ptr->next;
}

}

至少重写for循环，例如

while ( ptr != NULL && positionFromTail-- )
{
ptr = ptr->next;
}
if ( ptr != NULL )
{
return ptr->data;
}
else
{
// return some value
return  -1;
}

参数positionFromTail必须是无符号整数类型。否则，您需要在函数开始时检查它是否为负值。

注意，退出函数后，列表将被打破。调用函数后，main中的指针头不会改变，但指针所指向的节点和其他节点的数据成员next的值会改变。所以总的来说，你的方法是不正确的。

不需要反转列表来查找从列表末尾开始计算的给定位置的元素。

对于初学者，我将以以下方式声明函数

int getNode( const struct Node *head, int pos, int *data );

即如果存在具有指定位置的节点，该函数返回1，否则返回0。如果存在指定位置的节点，则将存储值写入解引用参数data。

如果参数pos的值不为负，则从列表的头部开始计数，否则从列表的末尾开始计数。

这是一个示范程序。

#include <stdlib.h>
#include <stdio.h>
struct Node 
{
int data;
struct Node *next;
};
void clear( struct Node **head )
{
while (*head)
{
struct Node *current = *head;
*head = ( *head )->next;
free( current );
}
}
size_t create( struct Node **head, const int a[], size_t n )
{
clear( head );
size_t i = 0;
while (n-- && ( *head = malloc( sizeof( struct Node ) ) ) != NULL )
{
( *head )->data = *a++;
( *head )->next = NULL;
++i;
head = &( *head )->next;
}
return i;
}
FILE * display( const struct Node *head, FILE *fp )
{
for (; head != NULL; head = head->next)
{
fprintf( fp, "%d -> ", head->data );
}
fputs( "null", fp );
return fp;
}    
int getNode( const struct Node *head, int pos, int *data )
{
int success = 0;
if (!( pos < 0 ))
{
while (head != NULL && pos--)
{
head = head->next;
}
if (( success = head != NULL )) *data = head->data;
}
else
{
const struct Node *current = head;
for ( ;current != NULL && pos; ++pos )
{
current = current->next;
}
while (current != NULL )
{
head = head->next;
current = current->next;
}
if (( success = pos == 0 )) *data = head->data;
}
return success;
}
int main( void )
{
struct Node *head = NULL;
const int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
create( &head, a, sizeof( a ) / sizeof( *a ) );
fputc( 'n', display(head, stdout ) );
for (int i = 0, data; getNode( head, i, &data ); i++)
{
printf( "%d: %d; ", i, data );
}
putchar( 'n' );
for (int i = -1, data; getNode( head, i, &data ); i--)
{
printf( "%d: %d; ", i, data );
}
putchar( 'n' );
clear( &head );
}

程序输出为

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
0: 0; 1: 1; 2: 2; 3: 3; 4: 4; 5: 5; 6: 6; 7: 7; 8: 8; 9: 9;
-1: 9; -2: 8; -3: 7; -4: 6; -5: 5; -6: 4; -7: 3; -8: 2; -9: 1; -10: 0;