【剑指offer】面试题22-链表的倒数第k个结点

2020-02-08
阅读量 | 字数：499字 | 预计阅读时长：2分钟

题目

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

1. 思路

第一次遍历链表，计算链表长度length；
第二次遍历链表，让指针向后移动length - k次，就可以得到倒数第k个结点。

2.代码（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) {
        if (head == null) {	// 空链表，返回null
        	return null;	
        }
    	ListNode p = head, r = head;
        int  len = 0;
        while(r != null){
            r = r.next;
            len ++;			// 计算链表长度
        }
        if (len < k){		// 判断k值是否合法
            return null;	// 如果k值比链表长度还大，不合法，返回null
        }
        for (int i = 0; i < len - k; i++) {
        	p = p.next;		// 指针向后移动length-k次。得到目标结点
        }   
        return p;
    }
}

补充

如果我们输入的链表和k值都合法，那么这个题其实用下面的说法更好理解一些。
思路
设两个指针first 和second ，初始时均指向头结点，first 向后移动k - 1次，此时first 指向的是正数第k个结点，在这之后，当first的后继节点不为空时，second和first就同时后移，当first的后继节点为空，就说明first已经指向了链表的尾结点，那此时second指向的结点，就是倒数第k个结点，因为first和second之间的距离刚好是k-1。各位看官老爷画图看看就会明白了，很容易理解。
代码

class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
    	if (head == null) {
        	return null;
        }
    	ListNode first = head, second = head;
    	int count = 1;// 计数器count，初始化为1，因为已经指向了头结点
        while(first.next != null) {
        	if (count < k)				// first先后移走 k - 1 次
        		count ++;
        	else {
        		second = second.next; 	// second跟随后移
        	}
        	first = first.next;
        }  
        return r;
    }
}

PS：印象里苏大计算机考研有个编程题是写这个，倒数第k个结点。

本文作者： whtli
本文链接： https://hexo.whtli.cn/archives/e31dcbb2.html
版权声明： 遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。