链表二：链表中倒数第k个结点

题目：链表中倒数第k个结点
描述：输入一个链表，输出该链表中倒数第k个结点。
解决方案：思路：根据规律得出倒数第k个节点是 n-k+1个节点

方法一：先计算出链表的长度,在循环走到n-k+1步。（相当于去掉链表最后k-1个元素，然后求此时链表最后一个元素）
方法二：两个指针指向头结点，第一个指针走k-1步，第二个指针不懂，然后两个指针同时往后移。第一个指针到了链表结尾的时候，第二个指针的位置是就是所求的位置；（做了一把K-1长度的尺子）


public class ListOne {

	　　public static void main(String[] args) {

		　　　　ListNode node1 = new ListNode(1);

		　　　　ListNode node2 = new ListNode(2);

		　　　　ListNode node3 = new ListNode(3);

		　　　　ListNode node4 = new ListNode(4);

		　　　　ListNode node5 = new ListNode(5);

		　　　　ListNode node6 = new ListNode(6);

		　　　　ListNode node7 = new ListNode(7);

		　　　　node1.next = node2;

		　　　　node2.next = node3;

		　　　　node3.next = node4;

		　　　　node4.next = node5;

		　　　　node5.next = node6;

		　　　　node6.next = node7;

		　　　　System.out.println(find(node1,3));

	　　}

　　//方法一：

	　　public static int find(ListNode node ,int k) {

		　　　　ListNode resultNode = node;

		　　　　int result = 0;

		　　　　int count = 0;

　　　　while(node!=null) {

			　　　　　　count++;

			　　　　　　node = node.next;

		　　　　}

　　　　if(k ==0 || k > count) return -1;

		　　　　for(int i=0;i<= count-k;i++) {

			　　　　　　result = resultNode.val;

			　　　　　　resultNode = resultNode.next;

		　　　　}

		　　　　return result;

	　　}

	　　//方法二

　　public ListNode static find(ListNode node ,int k){

　　　　if(node == null || k<0 ) return null;

　　　　ListNode one=node ,two = node;

   　　for(int i = 1;i<k ;i++){  //第一个指针先走k-1步

　　　　　　if(one.next != null;){

　　　　　　　　one = one.next;

　　　　　　}else {

　　　　　　　　return null;

　　　　　　}

　　　　}

　　　　while(one.next!= null){

　　　　　　one = one.next;

　　　　　　two = two.next;

　　　　}

　　　　　　return  two;

　　}

}

class ListNode{

	　　int val;

	　　ListNode next;

	　　ListNode(int val){

		　　　　this.val = val;

	　　}

}

巴特西

链表二：链表中倒数第k个结点

最新文章

热门文章