【剑指Offer】链表中倒数第k个结点

Posted on | In ,

题目

输入一个链表，输出该链表中倒数第k个结点。例如一个链表有6个结点，从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点。

实现

1
2
3
4
5
6
7
8
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode FindKthToTail(ListNode head, int k) {
    if (k == 0 || head == null)
        return null;

    ListNode ahead = head;
    ListNode behind = head;

    for (int i = 1; i < k; i++) {
        if (ahead.next == null)
            return null;

        ahead = ahead.next;
    }

    while (ahead.next != null){
        ahead = ahead.next;
        behind = behind.next;
    }

    return behind;
}

相关题目

  1. 求链表的中间结点。如果链表中结点总数为奇数，返回中间结点；如果结点总数是偶数，返回中间两个结点的任意一个。我们也可以定义两个指针，同时从链表的头结点出发，一个指针一次走一步，另一个指针一次走两步。当走得快的指针走到链表的末尾时，走得慢的指针正好在链表的中间。

  2. 判断一个单向链表是否形成了环形结构。定义两个指针，同时从链表的头结点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就是环形链表；如果走得快的指针走到了链表的末尾都没有追上第一个指针，那么链表就不是环形链表。