剑指offer链表中倒数第k个结点

素颜马尾好姑娘i 2021-09-19 18:38 391阅读 0赞

*  题目:输入一个链表，输出该链表中倒数第K个节点；为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第一个结点。
 *  题目分析：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfc2h1eXU_size_16_color_FFFFFF_t_70]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfc2h1eXU_size_16_color_FFFFFF_t_70 1]
    
     *  代码如下：

public class LinkK { 
    
    	public static LinkNode getReciprocalK(LinkNode linkNode,int k){ 
    		//头指针
    		LinkNode head=linkNode;
    		//与头指针相隔k的尾指针
    		LinkNode behind=null;
    		//让头指针与尾指针相隔距离为k
            for (int i=0;i<k-1;i++){ 
            	head=head.next;
    		}
            behind=linkNode;
            //头指针和尾指针一同向下遍历，只到头指针到达链表尾节点
            while (head.next!=null){ 
            	head=head.next;
            	behind=behind.next;
    		}
            return behind;
    	}
    
    	public static void main(String[] args) { 
    		LinkNode head1 = new LinkNode(1);
    		LinkNode  head2 = new LinkNode(2);
    		LinkNode  head3 = new LinkNode(3);
    		LinkNode  head4 = new LinkNode(4);
    		LinkNode  head5 = new LinkNode(5);
    		head1.next=head2;
    		head2.next=head3;
    		head3.next=head4;
    		head4.next=head5;
    
    		LinkNode reciprocalK = getReciprocalK(head1, 4);
    		System.out.println(reciprocalK.data);
    
    	}
    }

github代码地址;[https://github.com/iot-wangshuyu/offer/tree/master/code/src/linkK][https_github.com_iot-wangshuyu_offer_tree_master_code_src_linkK]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfc2h1eXU_size_16_color_FFFFFF_t_70]: /images/20210901/cb45b637c122408cb535799aa8007eff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfc2h1eXU_size_16_color_FFFFFF_t_70 1]: /images/20210901/6b5795c1a79549ffad41eeb4ba6f1a2b.png
[https_github.com_iot-wangshuyu_offer_tree_master_code_src_linkK]: https://github.com/iot-wangshuyu/offer/tree/master/code/src/linkK