By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、找出单链表中倒数第K个元素

找出单链表中倒数第K个元素

例如给定单链表：1->2->3->4->5->6->7，则单链表的倒数第k=3个元素为5.

1.1、解题思路

1.2、算法

1.2.1、算法1-遍历两次

public ListNode findLastK1(ListNode head, int k) {
  ListNode listNode = head;
  int n = 0;
  while (listNode != null) {
    n++;
    listNode = listNode.next;
  }

  int i = 1;
  while (i <= n - k) {
    listNode = listNode.next;
    i++;
  }
  return listNode;
}



// 初始化数据
public ListNode listNode() {
  ListNode listNode_5 = new ListNode(5, null);
  ListNode listNode_4 = new ListNode(4, listNode_5);
  ListNode listNode_3 = new ListNode(2, listNode_4);
  ListNode listNode_2 = new ListNode(1, listNode_3);
  ListNode listNode_1 = new ListNode(0, listNode_2);
  return listNode_1;
}

class ListNode {
  int val;
  ListNode next;

  public ListNode(int val) {
    this.val = val;
  }

  public ListNode(int val, ListNode next) {
    this.val = val;
    this.next = next;
  }
}

1.2.2、算法2-遍历一次

public ListNode findLastK2(ListNode head, int k) {
  ListNode list1 = head;
  ListNode list2 = head;
  for (int i = 0; i < k - 1 && list1 != null; i++) {
    list1 = list1.next;
  }

  while (list1 != null) {
    list1 = list1.next;
    list2 = list2.next;
  }
  return list2;
}



// 初始化数据
public ListNode listNode() {
  ListNode listNode_5 = new ListNode(5, null);
  ListNode listNode_4 = new ListNode(4, listNode_5);
  ListNode listNode_3 = new ListNode(2, listNode_4);
  ListNode listNode_2 = new ListNode(1, listNode_3);
  ListNode listNode_1 = new ListNode(0, listNode_2);
  return listNode_1;
}

class ListNode {
  int val;
  ListNode next;

  public ListNode(int val) {
    this.val = val;
  }

  public ListNode(int val, ListNode next) {
    this.val = val;
    this.next = next;
  }
}

1.3、测试

​

ContactAuthor