剑指offer 14. 链表中倒数第 k 个结点

14. 链表中倒数第 k 个结点

题目描述

输入一个链表，输出该链表中倒数第k个结点

法一：快慢指针

快指针先走 k 步，等快指针到达尾部时，慢指针所指结点即是倒数第 k 个结点

 1 public class Solution {
 2     public ListNode FindKthToTail(ListNode head,int k) {
 3        // 快慢指针
 4         if(head == null){
 5             return null;
 6         }
 7         ListNode fast = head;
 8         ListNode low = head;
 9         for(int i = 0; i < k; i++){
10             if(fast == null){            // 链表长度不足 k 则返回 null
11                 return null;
12             }
13             fast = fast.next;
14         }
15         
16         while(fast != null){
17             fast = fast.next;
18             low = low.next;
19         }
20         return low;
21     }
22 }

leetcode运行时间为 0ms, 空间为36.6mb

另一种写法

 1 class Solution {
 2     public ListNode getKthFromEnd(ListNode head, int k) {
 3         // 让快指针先走k步，随后快慢指针同时走
 4         ListNode low = head, fast = head;
 5         int cnt = 1;        // low已经指向了第一个结点
 6         while(fast != null){
 7             fast = fast.next;
 8             if(cnt > k){
 9                 low = low.next;
10             }
11             cnt++;
12         }
13         if(cnt < k){    // 如果链表结点个数小于k,直接返回null
14             return null;
15         }else{
16             return low;
17         }
18     }
19 }

leetcode运行时间为1ms, 空间为：37.3mb

复杂度分析：

时间复杂度：O(n)

空间复杂度：O(1)

法二：遍历两次

第一次遍历链表统计链表长度，再次遍历链表，遍历到的第len - k个结点即是倒数第k个结点。注意链表为空和 k 超出链表长度的特殊情况

 1 class Solution {
 2     public ListNode getKthFromEnd(ListNode head, int k) {
 3 
 4         // 遍历链表统计链表长度
 5         int len = 0;
 6         ListNode p = head;
 7         while(p != null){
 8             len++;
 9             p = p.next;
10         }
11 
12         // 如果链表长度小于k, 直接返回null
13         if(len < k){
14             return null;
15         }
16 
17         // 再次遍历链表，遍历到的第len - k个结点即是倒数第k个结点
18         p = head;
19         for(int i = 0; i < len - k; i++){
20             p = p.next;
21         }
22         return p;
23     }
24 }

leetcode运行时间为0ms, 空间为37.1MB