【数据结构】求链表的第m个元素

题目链接

习题3.5 求链表的倒数第m个元素 - 浙大版《数据结构（第2版）》题目集

整体思路

将链表反转之后遍历至第m个元素

其中，链表反转实现方法：定义一个新链表，使用尾插法逐个将原链表的结点插入

代码

ElementType Find( List L, int m )
{PtrToNode ptrL, ptrL2, tmpNode;List L2 = (List) malloc(sizeof(struct Node));int i = 1;int ret = 0;// 跳过头结点ptrL = L->Next;// 新建链表，存放反转后的链表LL2->Next = NULL;// 遍历L，头插法插到L2while (ptrL != NULL){tmpNode = (PtrToNode) malloc(sizeof(struct Node));tmpNode->Data = ptrL->Data;tmpNode->Next = L2->Next;L2->Next = tmpNode;ptrL = ptrL->Next;}// 跳过头结点ptrL2 = L2->Next;// 从L2中查找除头结点外第m个结点while (i < m && ptrL2 != NULL){ptrL2 = ptrL2->Next;i++;}if (i == m){// 找到第m个结点ret = ptrL2->Data;}else{// 遍历到链表尾，没到第m个结点ret = ERROR;}return ret;
}