2020-07-15 leetcode 面试题 02.02.

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

注意：本题相对原题稍作改动

示例：

输入： 1->2->3->4->5 和 k = 2
输出： 4
说明：

给定的 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) {
        int size = 0;
        if(head == null){//链表为空
            return 0;
        }
        ListNode cur = head;
        while(true){
            size++;
            if(cur.next==null){
                break;
            }
            cur = cur.next;
        }
        int num = size - k;
        cur = head;
        while(num!=0){
            cur = cur.next;
            num--;
        }
        return cur.val;
    }
}

解法二：快慢指针
fast指针比slow指针快k个节点，所以fast到队尾的时候slow就是倒数第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) {
       //快慢指针
         if(head == null){//链表为空
            return 0;
        }
        ListNode slow = head;
        ListNode fast = head;
        int count = k;
        while(k!=0){
            fast = fast.next;
            k--;
        }
        while(fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
}