剑指offer(牛客)---链表中倒数第k个结点

题目描述

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

这道题首先按照普通的方法用一个栈来存放链表数据然后在取出第k的数就可以了,但是这种方法的时间复杂度是O(n),不提倡;

现在我介绍一种时间复杂度为O(n-k)的方法,老规矩-->先贴源码,在分析:

    /*
    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(k==0){
                return null;
            }
            if(head==null) {
        		return head;
        	}
        	if(head.next==null) {
        		return head;
        	}
        	ListNode scale=head;
        	for(int i=1;i<k;i++) {
                if(scale.next!=null){
        		scale=scale.next;
                }else{
                    return null;
                }
        	}
        	ListNode anw=head;
        	while(scale.next!=null) {
        		scale=scale.next;
        		anw=anw.next;
        	}
    		return anw;
        }
    }

这个解法的巧妙之处在于突破了编程的固定思维,采用一种独特的方式解决;

巧妙之处在于使用了一个变量当做刻度尺,来量出它的长度,这也是该算法的核心.现在开始进行案例分析:

假设head中数据为{1,2,3,4,5},如下图所示

假设k值是2,现在定义一个刻度尺变量int scale=0,由于k值是2,那么循环(k-1)次,scale通指向

    for(int i=1;i<k;i++) {
                if(scale.next!=null){
        		scale=scale.next;
                }else{
                    return null;
                }
        	}

指向如下图所示(现在的指向其实是前面数第k个,现在就相当于定义好了一个刻度尺一样,开始测量):

刻度值变量scale指向了从前面数第k个变量,现在使用 ListNode anw=head;即anw以scale为标准进行移动:

首先第一次while(scale.next!=null)之后:

第二次 while(scale.next!=null)之后:

第三次 while(scale.next!=null)之后:

第四次 while(scale.next!=null): scale.next==null,结果已经出来了,anw指向了倒数第k个值;

总结:该算法的巧妙之处,通过从前面考虑,以一个变量当做刻度尺一步步next,真的太精妙了!