题目: 写一个方法返回一个单向链表中倒数第 k 个元素. 比如, 3->1->4->1->5->9->2->6 那么倒数第三个元素是 9 所以该方法应该返回 9
思路: 这道题挺好想的 就是算出来倒数第 k 个元素是正数第几个 然后找到这个元素 当然这是我们知道链表 size 的情况 代码如下
class MyLinkedList2 extends SinglyLinkedList{public MyLinkedList2(){super();}public E mySolution(int k){if(super.size()return null;int position &＃61; super.size()-k;Node target &＃61; super.findFirst();for(int i&＃61;0; i target.next();return target.data();}
}
此方法的时间复杂度是 O(k) 空间复杂度是 O(1)
让然 如果不知道链表的 size, 就稍微难想一点了
思路是这样的 我们使用两个指针同时指向 head 然后我们将其中一个指针 移动到正数第 k 个元素上 让另一个指针保持不动, 然后我们让两个指针同时向前移动 当前面的指针指向链表末端的时候 后面的指针应该刚好达到链表的倒数第 k 个元素 代码如下
class MyLinkedList2 extends SinglyLinkedList{public MyLinkedList2(){super();public E anotherSolution(int k){if(k<&＃61;0) return null;Node p1 &＃61; super.findFirst();Node p2 &＃61; super.findFirst();for(int i&＃61;0; i){if(p2&＃61;&＃61;null) return null;p2 &＃61; p2.next();}if(p2&＃61;&＃61;null) return null;while(p2.next()!&＃61;null){p1 &＃61; p1.next();p2 &＃61; p2.next();}return p1.data();}
}
此方法的时间复杂度和空间复杂度 和第一个方法一样 只不过此方法可以再不知道链表 size 的情况下完成任务
京公网安备 11010802041100号