code4offer-10 链表中倒数第k个节点

链表中倒数第k个节点

问题描述

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

分析

使用快慢指针法

初始slow指针指向头节点，fast指针头节点后k-1个节点，两个指针都向后移动，直到fast到达链表尾部

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    if (pListHead == NULL) return NULL;
    ListNode* slow = pListHead;
    ListNode* fast = pListHead;

    while(--k > 0) {
        if (fast->next != NULL) {
            fast = fast->next;
        } else {
            return NULL;
        }
    }

    while (fast->next != NULL) {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}

简洁点可以将两个while合并成一个

这个是用java写的因为C++版的死活不通过，后来才发现C++版的k是unsigned int，不会 < 0，可以直接删掉unsigned或者用个int存下k就能通过了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode getKthFromEnd(ListNode head, int k) {
    if (head == null) return head;
    ListNode fast = head;
    ListNode slow = head;

    while (fast != null) {
        if (--k < 0) {
            slow = slow.next;
        }

        fast = fast.next;
    }

    if (k > 0) return null;
    return slow;
}