【剑指offer】-链表中倒数第K个结点-14/67-阿里云开发者社区

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

2023-12-28 32

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

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

1. 题目描述

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

假设题目为： 3 【1,2,3,4,5,6】

2. 题目思路

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

1 判断当前给的链表head是不是null，如果是的话，返回null

2. 判断k的值，如果k的值，小于等于0，返回null

3. 建立两个结点，指向head(注意：这里一定要明白当前链表是不是有头结点的，该题不含有头结点)

4. 先让p1结点跑k-1(2)次(要时刻注意，p1.next是否走到了null)

5. 然后p1和p2同时开始跑，等到p1.next跑到null时，p2所指的指针就是倒数第K(3)个结点

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

1 判断当前给的链表head是不是null，如果是的话，返回null

2. 判断k的值，如果k的值，小于等于0，返回null

3. 建立一个结点，遍历一遍链表，找到链表的长度len

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;
  }