查找单链表中倒数第m个元素代码,C代码库,德仔网

代码语言

代码分类

【C】查找单链表中倒数第m个元素

作者:Dezai.CN / 发布于2011/7/21/ 831

<div>
<span style="font-family: Verdana; font-size: 16px">element *CLinkList::FindMToLastElement(int m)</span>
<span style="font-family: Verdana; font-size: 16px">{</span>
<span style="font-family: Verdana; font-size: 16px">element *previous, *current;</span>
<span style="font-family: Verdana; font-size: 16px">previous = current = head;</span>
<span style="font-family: Verdana; font-size: 16px">// 访问前m-1个节点</span>
<span style="font-family: Verdana; font-size: 16px">for(int i = 0; i < m-1; ++i)</span>
<span style="font-family: Verdana; font-size: 16px">{</span>
<span style="font-family: Verdana; font-size: 16px">current = current->next;</span>

<span style="font-family: Verdana; font-size: 16px">if(current == NULL)</span>
<span style="font-family: Verdana; font-size: 16px">{</span>
<span style="font-family: Verdana; font-size: 16px">//</span><span style="font-family: Courier New"><span style="font-family: Verdana; font-size: 16px">不到</span><span style="font-family: Verdana; font-size: 16px">M</span><span style="font-family: Verdana; font-size: 16px">个元素</span></span>
<span style="font-family: Verdana; font-size: 16px">return NULL;</span>
<span style="font-family: Verdana; font-size: 16px">}</span>
<span style="font-family: Verdana; font-size: 16px">}</span>
<span style="font-family: Verdana; font-size: 16px">//previous指针和current指针一起向尾移动</span>
<span style="font-family: Verdana; font-size: 16px">while(current->next != NULL)</span>
<span style="font-family: Verdana; font-size: 16px">{</span>
<span style="font-family: Verdana; font-size: 16px">previous = previous->next;</span>
<span style="font-family: Verdana; font-size: 16px">current = current->next;</span>
<span style="font-family: Verdana; font-size: 16px">}</span>
<span style="font-family: Verdana; font-size: 16px">//返回previous指针</span>
<span style="font-family: Verdana; font-size: 16px">return previous;</span>
<span style="font-family: Verdana; font-size: 16px">}</span>
<span style="font-family: Verdana; font-size: 16px">
<span style="font-family: Verdana; font-size: 16px">在整个算法中只使用了两个辅助指针previous和current，所以空间复杂度为O(1)，即常数。由于整个过程只访问了链表一遍，所以时间复杂度为O(n)，即为线性时间。综上所述，该算法时间复杂度和空间复杂度都比较低，是一个优化的算法。</span>
</span></div>

试试其它关键字

　单链表中倒数第m个元素　

同语言下

可能有用的

Dezai.CN贡献的其它代码(4037)