求单链表中有效节点的个数

代码思路

求单链表中有效节点的个数：遍历即可

代码实现

  1. /**
  2.  * 方法：获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点)
  3.  * @return 返回的就是有效节点的个数
  4.  */
  5. public int length() {
  6.     if (this.head.next == null) {
  7.         System.out.println("链表为空");
  8.         return 0;
  9.     }
  10.     // 定义一个辅助的变量, 这里我们没有统计头节点
  11.     HeroNode cur = this.head.next;
  12.     int length = 0;
  13.     while (cur != null) {
  14.         length++;
  15.         cur = cur.next;
  16.     }
  17.     return length;
  18. }

测试:

  1. public class SingleLinkedListDemo {
  2.     public static void main(String[] args) {
  3.         // 进行测试
  4.         // 先创建节点
  5.         HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  6.         HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  7.         HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  8.         HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
  9.         SingleLinkedList singleLinkedList = new SingleLinkedList();
  11.         System.out.println("链表长度: " + singleLinkedList.length());
  12.     }
  13. }

查找单链表中的倒数第 k 个结点

代码思路

  • 查找单链表中的倒数第k个结点 【新浪面试题】

    • 首先，获取整个链表中元素的个数 size
    • 在使用 for 循环定位至倒数第 index（形参） 个节点，返回即可
    • for 循环的条件应如何确定？for (int i = 0; i < x; i++) 中 x 的值应是多少？我们需要定位至倒数第 index 个节点，在 for 循环之前，我们已经定位置首节点，还需再走 (size - index ) 步，定位至倒数第 index 个节点

    • 举例说明：链表中一共有 4 个元素，想要定位至倒数第 2 个节点，那么需要在首节点之后走两步，到达倒数第 2 个节点

      代码实现

      1. /**
      2. * 查找单链表中的倒数第k个结点
      3. *
      4. * 查找单链表中的倒数第k个结点 【新浪面试题】
      5. * 思路
      6. * 1. 编写一个方法，接收head节点，同时接收一个index
      7. * 2. index 表示是倒数第index个节点
      8. * 3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
      9. * 4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
      10. * 5. 如果找到了，则返回该节点，否则返回null
      11. */
      12. public HeroNode findLastIndexNode(int index) {
      13. // 判断如果链表为空，返回null
      14. if (this.head.next == null) {
      15.    System.out.println("链表为空");
      16.    return null;
      17. }
      19. // 第一个遍历得到链表的长度(节点个数)
      20. int size = length();
      21. // 第二次遍历 size-index 位置，就是我们倒数的第K个节点
      22. // 先做一个index的校验
      23. if (index <= 0 || index > size) {
      24.    return null;
      25. }
      26. HeroNode cur = this.head.next;
      27. // 定义给辅助变量， for 循环定位到倒数的index
      28. for (int i = 0; i < size - index; i++) {
      29.    cur = cur.next;
      30. }
      31. return cur;
      32. }



      测试:

      1. public class SingleLinkedListDemo {
      2. public static void main(String[] args) {
      3.    // 进行测试
      4.    // 先创建节点
      5.    HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
      6.    HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
      7.    HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
      8.    HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
      9.    SingleLinkedList singleLinkedList = new SingleLinkedList();
      11.    System.out.println("查找倒数第n个node: " + singleLinkedList.findLastIndexNode(2));
      12. }
      13. }