Kth to Last

出处

Find the kth to last element of a singly linked list. For example, if given a list 1->2->3->4, and k equals to 2, the function should return element 2.

Solution

由于题目涉及在链表中寻找特定位置,我们用两个指针变量遍历该list。只是在本例中,runner与chaser以相同倍速前进,但runner提前k步出发。

Complexity

只要遍历一次,时间复杂度 O(n)

Code

Node kthtolast(Node head, int k){
    if (head == null) return null;
    if (k < 0) return null;
    
    Node quick = head;
    Node slow = head;
        
    for (int i = 0; i < k; i++){
        if (quick.next != null)
            quick = quick.next
    }
    
    while (quick != null){
        slow = slow.next;
        quick = quick.next;
    }
    
    return slow;
}