JZ14 — 链表中倒数第k个结点

题目描述

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

解法一

找个容器将链表保存下来，然后输出倒数第k个元素。
时间复杂度为O(n)，空间复杂度为O(n)
这种解法由于需要额外开容器，占用内存空间，所以并不是一个优雅的解法。

C++

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution
{
public:
    ListNode *FindKthToTail(ListNode *pListHead, unsigned int k)
    {
        vector<ListNode *> v;
        while (pListHead != NULL)
        {
            v.push_back(pListHead);
            pListHead = pListHead->next;
        }
        if (k > v.size())
            return NULL;
        return v[v.size() - k];
    }
};

Java

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.*;

public class Solution {
    public ListNode FindKthToTail(ListNode head, int k) {
        ArrayList<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        if (k > list.size() || k <= 0)
            return null;
        return list.get(list.size() - k);
    }
}

解法二

遍历一遍，记录结点的总数size，然后再遍历一遍，输出正向第size-k+1个结点。
时间复杂度为O(n)，空间复杂度为O(1)

C++

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution
{
public:
    ListNode *FindKthToTail(ListNode *pListHead, unsigned int k)
    {
        int size = 0, index = 0;
        for (ListNode *p = pListHead; p != NULL; p = p->next)
            size++;
        if (k > size)
            return NULL;
        for (ListNode *p = pListHead; p != NULL; p = p->next)
        {
            if (++index == size - k + 1)
                return p;
        }
    }
};

Java

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head, int k) {
        int size = 0, index = 0;
        for (ListNode p = head; p != null; p = p.next)
            size++;
        if (k > size || k <= 0)
            return null;
        for (ListNode p = head; p != null; p = p.next)
            if (++index == size - k + 1)
                return p;
        return null;
    }
}

解法三

使用两个指针left和right从左到右遍历，两指针中间相差k个结点，当right到达末尾指向NULL的时候，left对应的就是倒数第k个结点。
时间复杂度为O(n)，空间复杂度为O(1)

C++

class Solution
{
public:
    ListNode *FindKthToTail(ListNode *pListHead, unsigned int k)
    {
        ListNode *left = pListHead, *right = pListHead;
        int count = 0;
        while (right)
        {
            count++;
            right = right->next;
            if (count > k)
                left = left->next;
        }
        if (count < k)
            return NULL;
        return left;
    }
};

Java

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head, int k) {
        int count = 0;
        ListNode left = head, right = head;
        while (right != null) {
            right = right.next;
            if (++count > k)
                left = left.next;
        }
        if (count < k || k <= 0)
            return null;
        return left;
    }
}