剑指 Offer 22. 链表中倒数第k个节点
输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。
例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例:
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
看到题目,首先想到的是统计链表长度,然后根据链表长度找到对应位置的节点,但这个如果链表很长的话,暴力求解消耗的时间就会比较长了。
可以使用双指针,这种方法不用计算链表的长度。
首先former指针先向后移动k个节点,然后later指针指向头结点,和former指针一起向后遍历到链表尾部,此时later指针指向的就是倒数第k个节点。
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode later = head,former = head;
// 考虑到特殊情况
if(head == null || k <= 0) return null;
for(int i = 0;i < k; i++){
// 考虑k大于链表长度的情况
if(former == null) return null;
former = former.next;
}
while(former != null){
later = later.next;
former = former.next;
}
return later;
}
万事开头难,有一件事没做,一直拖延怎么办?
先给自己5-10分钟的时间,什么都不想,立刻开始去做那件事,开了这个头,5-10分钟之后,自然而然地就会一直做下去了。如果在做事情的过程中,中断了或者走神了,也可以继续使用这种方法。
《拖延心理学》说:当有某件事我们必须做,某些规则必须遵守时,我们会产生逆反心理。拖延,是我们对这种被掌控的状态,作出的反抗。
人讨厌急迫被追赶的状态,针对这种心理,我们可以每天做的比计划多一点,给自己留下更多的弹性空间和时间,让自己对事情有更多的掌控感,更有助于我们每天积极地去完成计划。
还没有评论,来说两句吧...