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

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

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

示例：

1
2
3
给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

算法思路：

解法1：

  • 假设链表长度为n，倒数第k个即正数第n-k个
  • 两次遍历，第一次找出链表长度，第二次找到链表第n - k个结点

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode cur = head;
    int length = 0;
    
    while(cur != null){
        length++;
        cur = cur.next;
        
    }
 
    if(length < k ){
        return null;
    }
    cur =head;
    for(int i = 0;i < length - k;i++){
        cur = cur.next;
    }
    return cur;

}

解法2：

  • 双指针
  • 快指针先走k步，然后慢指针和快指针同步走
  • 快指针走到链表末尾，慢指针走到倒数第k个结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public ListNode getKthFromEnd(ListNode head, int k) {
    //双指针，快指针先走k步，然后慢指针和快指针同步走，快指针走到链表末尾，慢指针走到倒数第k个结点

    if (head == null || k <= 0) {
        return null;
    }

    ListNode fast = head;
    ListNode slow = head;

    //快指针扫描链表长度，边走边判断是否到达了链表尾部，因为链表长度可能小于k
    while (fast != null && k > 0) {
        --k;
        fast = fast.next;
    }
    //如果链表长度小于k，直接返回空
    if (k > 0) {
        return null;
    }

    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    return slow;


}