【剑指offer】-链表中倒数第K个结点-14/67

Bertha 。 2023-07-20 12:24 10阅读 0赞

# 1. 题目描述 #

输入一个链表，输出该链表中倒数第k个结点  
假设题目为： 3 【1,2,3,4,5,6】

# 2. 题目思路 #

## 2.1 第一种思路：两个结点分别跑 ##

1 判断当前给的链表head是不是null，如果是的话，返回null  
2. 判断k的值，如果k的值，小于等于0，返回null  
3. 建立两个结点，指向head(注意：这里一定要明白当前链表是不是有头结点的，该题不含有头结点)  
![链表][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]  
4. 先让p1结点跑k-1(2)次(要时刻注意，p1.next是否走到了null)![在这里插入图片描述][20200401175027703.png]  
5. 然后p1和p2同时开始跑，等到p1.next跑到null时，p2所指的指针就是倒数第K(3)个结点![在这里插入图片描述][20200401175139296.png]

## 2.2 第二种思路：一个结点跑 ##

1 判断当前给的链表head是不是null，如果是的话，返回null  
2. 判断k的值，如果k的值，小于等于0，返回null  
3. 建立一个结点，遍历一遍链表，找到链表的长度len![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 1]  
4. 重新定义结点p1，此时，**num = (len - k + 1)就是链表在结点中的位置，位置必须大于0**  
5. 此时链表p1指向第一个数值。所以，只需要跑**num - 1**次，即可找到倒数第K个数

# 3. 题目代码 #

## 3.1 第一种思路：两个结点分别跑 ##

public ListNode FindKthToTail(ListNode head,int k) {
        
               if(head == null || k <= 0){
        
                   return null;
               }
                ListNode p1 = head;
                ListNode p2 = head;
                for(int i = 0; i < k - 1; i++){
        
                    if(p1.next == null){
        
                        return null;
                    }else{
        
                        p1 = p1.next;
                    } 
                }
            while(p1.next != null){
        
                p1 = p1.next;
                p2 = p2.next;
            }
            return p2;
        }

## 3.2 第二种思路：一个结点跑 ##

public ListNode FindKthToTail(ListNode head, int k) {
        
    		if (head == null || k <= 0) {
        
    			return null;
    		}
    		ListNode p1 = head;
    		int len = 0;
    		while (p1 != null) {
        
                p1 = p1.next;
    			len++;
    		}
    		int num = len - k + 1;
            p1 = head;
    		if (num <= 0) {
        
    			return null;
    		}
    		for (int i = 1; i < num; i++) {
        
    			p1 = p1.next;
    		}
    		return p1;
    	}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]: /images/20230528/8e974bbb71e34eeeae75d982c4def1fb.png
[20200401175027703.png]: /images/20230528/919c715de4fa4213a6833895329b9ac9.png
[20200401175139296.png]: /images/20230528/b03b298ab0224cc2bce200cae5aa14aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 1]: /images/20230528/00e7be7a390c455f904e98fa71810790.png