剑指 Offer 22. 链表中倒数第k个节点

描述

None

tags: list, double pointer

思路

1. 两次遍历

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* node = head;
        int length = 0;
        while(node){
            length++;
            node = node->next;
        }
        while(length>k){
            head = head->next;
            length--;
        }
        return head;
    }
};

2. 一次遍历（双指针）

• 注意不要用while-loop

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* faster = head;
        for(int i = 0; i < k; i++){
            faster = faster->next;
        }
        //while(k){
        //    faster = faster->next;
        //    k--;
        //}
        while(faster){
            head = head->next;
            faster = faster->next;
        }
        return head;
    }
};