09 链表中找出倒数第k个数找出链表正中间的数据

本文主要是介绍09 链表中找出倒数第k个数找出链表正中间的数据，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

本博文部分图片, 思路来自于剑指offer 或者编程珠玑

问题描述

这里写图片描述

思路

对于找到倒数的第k个数 : 两个指针, 先让第一个指针先走k步, 然后两个指针一起移动, 直到第一个指针为null, 第二个指针指向的数据即为所求

对于找到中间数 : 同样两个指针, 一个指针每次移动两步, 另外一个指针每次移动一步, 到第一个指针为null的时候, 第二个指针即为所求

参考代码

/*** file name : Test30GetTheKthNumberInverseOrder.java* created at : 7:35:08 PM Jun 5, 2015* created by 970655147*/package com.hx.test04;public class Test30GetTheKthNumberInverseOrder {// 找到倒数第k个结点// 找到链表的中间结点public static void main(String []args) {int k = 3;LinkedList ll = new LinkedList();
//      LinkedList02 ll = new LinkedList02();ll.add(4);ll.add(2);ll.add(2);ll.add(5);ll.add(34);ll.add(51);Log.log(ll);getTheKthNumberInverseOrder01(ll.head.next, k);getCenter(ll.head.next);}// 思路 : 两个索引, 一个临时索引, 一个为元素索引// 先将临时索引  向前移动k-1步, 然后在同时移动tmp, ele索引, 知道临时索引 移动到链表末尾// 此时 元素索引即为所求public static void getTheKthNumberInverseOrder01(Node head, int k) {if(head == null || k <= 0) {return ;}Node ele = head, tmp = head;for(int i=0; i<k-1; i++) {if(tmp.next != null) {tmp = tmp.next;} else {return ;}}while(tmp.next != null) {tmp = tmp.next;ele = ele.next;}Log.log(ele.data );}// 获取链表的中间的那个节点, 如果元素个数是奇数  获取正中间的结点, 如果元素个数是偶数获取中间的两个结点之一// 思路 : 两个元素索引, 一个移动每次移动两步, 另一个每次移动一步// 当快的索引移动到链表结尾的时候, 慢的结点即为所求[若元素个数为偶数  则获取中间结点的前者]public static void getCenter(Node head) {if(head == null) {return ;}Node faster = head, slower = head;while(faster.next != null) {faster = faster.next;if(faster.next == null) {break ;}faster = faster.next;slower = slower.next;}Log.log(slower.data);}}