在单链表中查找第i个节点

海珠湖公园2022-07-21  24

单链表查找k节点 遍历一次链表

1.如果可以从链表的末尾开始遍历,那么只需要逆序遍历K个节点,也就是要查找的节点,但是由于是单链表,所以只能从起始节点开始遍历。

2.先遍历单链表,得到链表中节点总数N,那么第N-k+1个节点就是倒数第二个节点。所以第二次遍历到节点n-k+1就够了,但是题目要求链表只能遍历一次。

3.通过遍历链表,将所有节点存储在一个数组中,然后通过数组下标可以直接得到倒数第k个节点,但这样会需要额外的存储空,而空的复杂度为O(n)。

转载请注明原文地址:https://juke.outofmemory.cn/read/830891.html

最新回复(0)