【题22 链表中倒数第k个节点】

谁践踏了优雅 2022-03-25 01:52 172阅读 0赞

> 代码的鲁棒性  
> **鲁棒性：**  
> 指程序能够判断输入是否合乎规范要求，并对不符合要求的输入予以合理的处理  
> 提高鲁棒性方法：**防御性编程**  
> **防御性编程：**  
> 指预见在什么地方可能会出现问题，并为这些可能出现的问题指定处理方式  
> **最简单最实用的防御性编程是在函数入口添加代码，以验证用户输入是否符合要求。**  
> 考虑如果不。。。那么。。。

**【题22 链表中倒数第k个节点】**  
**【题目】**  
输入一个链表，输出该链表中倒数第k个节点，为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个节点。  
**例如：**  
一个链表有6个节点，从头节点开始，它们的值依次是1，2，3，4，5，6。这个链表的倒数第3个节点是值为4节点  
![在这里插入图片描述][20190118094521832.png]  
**法1**  
假设整个链表有n个节点，倒数第k个节点就是从头节点开始的第n-k+1个节点。如果知道n，那么只要从头节点开始往后走n-k+1步即可，如何得到n？遍历一遍即可。  
**即需要遍历两次：**

*  1.统计链表中节点个数：n
 *  2.找到倒数第k个节点。

**法2:定义两个指针**  
1． 第一个指针从链表的头指针开始遍历向前走k-1步  
2． 第二个指针保持不动，第k步开始，第二个指针也开始从链表头指针开始遍历  
两个指针距离保持在k-1，当第一个指针到达链表的尾结点时，第二个正好指向第k个节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
**有3种办法让代码崩溃：**

1.  输入的为空指针，由于代码会试图访问空指针指向的内存，从而造成程序的崩溃。
2.  输入的以。。。为头节点的链表的节点总数少于k，由于在for循环中，会在链表上向前走k-1步，仍然会由于空指针而造成程序崩溃。
3.  输入的参数k为0.由于k是一个无符号整数，那么在for循环中，k-1得到的将不是-1，而是4294967295，（无符号的0xFFFFFFFF）  
    因此for循环执行的次数远远超出我们的预计，同样也会造成程序崩溃

**分别处理：**

1.  如果输入的链表头指针是空，那么整个链表为空，此时查找倒数第k个节点自然应该返回空
2.  如果输入的k是0，也就是试图查找倒数第0个节点，由于我们计数从1开始，所有输入0 无实际意义，返回空，
3.  如果链表的节点少于k，那么在for循环中遍历链表可能会出现指向空的指针，因此，在for循环中应该加一个if判断

**【相关题目】**  
求链表的中间节点，如果链表中的节点总数为奇数，则返回中间节点，如果节点总数是偶数，则返回中间两个节点的任意一个，为了解决这个问题，我们也可以定义两个指针，同时从链表头节点出发，一个指针走一步，另一个指针以此走两步，当走得快的指针到达链表末尾时，走的慢的指针刚好在链表的中间  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]  
**【举一反三】**  
当我们用一个指针遍历不能解决问题时，可以尝试用2个指针来遍历链表，可以让其中一个指针遍历的速度快一些，（比如依次在链表上走2步）或者让它先在链表上走若干步。

**实现**

package ti22;
    
    public class Lianxi {
    	
    	public static ListNode findKthToTail(ListNode listHead,int k){
    		//参数校验（判断链表是否存在、k是否大于0）
    		if(listHead == null || k <= 0)
    			return null;
    		ListNode ahead = listHead;//前面的指针
    		
    		//先让ahead向前走k-1步
    		for(int i = 1;i <= k-1;i++){
    			if(ahead.next != null){
    				ahead = ahead.next;
    			}else	//当链表长度小于k时，则返回null
    				return null;
    		}
    		ListNode behind = listHead;//后面的指针
    		
    		while(ahead.next != null){
    			ahead = ahead.next;
    			behind = behind.next;
    		}
    		return behind;
    	}
    	
    	//主方法
    	public static void main(String[] args) {
    		ListNode head = new ListNode();
    		ListNode temp1 = new ListNode();
    		ListNode temp2 = new ListNode();
    		ListNode temp3 = new ListNode();
    		ListNode temp4 = new ListNode();
    		ListNode temp5 = new ListNode();
    		ListNode temp6 = new ListNode();
    		
    		head.value = 1;
    		temp1.value = 2;
    		temp2.value = 3;
    		temp3.value = 4;
    		temp4.value = 5;
    		temp5.value = 6;
    		temp6.value = 7;
    		
    		head.next = temp1;
    		temp1.next = temp2;
    		temp2.next = temp3;
    		temp3.next = temp4;
    		temp4.next = temp5;
    		temp5.next = temp6;
    		temp6.next = null;
    		
    		ListNode resultNode = findKthToTail(head,2);
    		if(resultNode != null)
    			System.out.println(resultNode.value);
    		else
    			System.out.println("您输入的参数有误！");
    	}
    
    }
    
    class ListNode{
    	int value;//节点值
    	ListNode next;//当前节点指向的下一个节点
    }

参考：  
1.《剑指offer》  
2.[https://blog.csdn.net/weixin\_37672169/article/details/80166543][https_blog.csdn.net_weixin_37672169_article_details_80166543]

[20190118094521832.png]: /images/20220325/295775c5ac0f404c86c49ff326a4ef58.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220325/0c8de6c4a0c94ac4bc7c28fa20e04b7d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]: /images/20220325/78e894ddd9ec4bd89b5bafc1de313b69.png
[https_blog.csdn.net_weixin_37672169_article_details_80166543]: https://blog.csdn.net/weixin_37672169/article/details/80166543