赞
踩
一、题目描述
二、解题思路
先通过一次遍历确定链表的长度,再找出倒数第k个节点。
三、编程实现
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public int kthToLast(ListNode head, int k) { ListNode h = head; int count = 1; while(h.next != null){ h = h.next; count ++; } h = head; for(int i = 0; i < count - k; i++){ h = h.next; } return h.val; } }
四、算法改进
采用双指针法,先让一个指针领先k个节点,再让两个指针同时推进直至先行的那个指针指向null为止。(并没有快很多)
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public int kthToLast(ListNode head, int k) { // 初始化前继节点与后继节点 ListNode previous = head; ListNode laterNode = head; // 后移后继节点,直到与前继节点距离相差为k for(int i=0;i<k;i++){ laterNode = laterNode.next; } // 同时移动前后继节点,直到后继节点值为空,此时前继节点值即为答案 while(laterNode!=null){ laterNode = laterNode.next; previous = previous.next; } return previous.val; } } 作者:GoogTech 链接:https://leetcode-cn.com/problems/kth-node-from-end-of-list-lcci/solution/mian-shi-ti-0202-fan-hui-dao-shu-di-k-ge-jie-di-23/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。