iOS常用算法之单链表查找倒数第n个节点(图解)
程序员文章站
2022-07-05 08:57:59
拿到题目, 首先要先了解链表数据结构, 如下图: 常规思路: 利用数组, 遍历整个单链表, 将每个节点装入数组中, 最终拿到数组根据索引(数组长度-1-n)就得到了倒数第n个元素. 简单思路: 假设总长度为n, 倒数第k个对应正数第n-k-1, 那么第一个指针移动k-1次, 第二个指针保持在head ......
拿到题目, 首先要先了解链表数据结构, 如下图:
常规思路: 利用数组, 遍历整个单链表, 将每个节点装入数组中, 最终拿到数组根据索引(数组长度-1-n)就得到了倒数第n个元素.
简单思路:
假设总长度为n,
倒数第k个对应正数第n-k-1,
那么第一个指针移动k-1次, 第二个指针保持在head不动;
第一个指针移动到尾部, 共移动n-k-1次, 那么第二个指针同步移动同样次数, 刚好指向第k个节点.
图解演算: