单链表常见面试题

• 2020 年 3 月 17 日
• 笔记

统计单链表中有效节点的个数

public class Test{      /**       * 获取单链表的有效节点的个数，不包括头节点       * @param head 链表的头节点       * @return 返回的是有效节点的个数       */      public static int getLength(HeroNode head){          if(head.next == null){ // 空链表              return 0;          }          int length = 0; //定义一个辅助的变量，从head.next开始统计，不统计头节点          HeroNode cur = head.next;          while (cur != null){              length++;              cur = cur.next;          }          return  length;      }  }

查找单链表中的倒数第k个节点（Sina）

public class Test{      /**       * 查找单链表中的倒数第k个节点       * 1. 通过遍历，得到链表的总长度       * 2. 得到长度后，链表的第size - index个，就是倒数第index个节点       * 3. 通过遍历获得size - index 节点，如果有返回节点，否则返回null       * @param head 头节点       * @param index 倒数第index个节点       * @return       */      public static HeroNode findLastIndexNode(HeroNode head,int index){          if(head.next == null){              return null; // 判断链表是否空，是返回null          }          int size = getLength(head);          if(index <= 0 || index > size){              return null; // 判断index是否小于0 或者 大于节点的个数，小于0或大于size返回null          }          HeroNode cur = head.next; // 定义辅助变量，通过辅助变量遍历链表，得到size - index，即倒数index          for(int i = 0; i < size - index;i++){              cur = cur.next;          }          return cur;      }  }

单链表的反转（Tencent）

第一次移动

第二次移动

第三次移动

public class Test{      /**       *  将单链表反转       * @param head       */      public static void reverseList(HeroNode head){          if(head.next == null || head.next.next == null){ // 链表为空，或只有1个节点，直接返回              return;          }            HeroNode cur = head.next; // 定义一个变量，用来遍历          HeroNode next = null; // 保存当前节点的下一个节点          HeroNode reverseHead = new HeroNode(0,"",""); // 创建一个新的链表            while (cur != null){              next = cur.next; // 暂时保存当前节点的下一个节点              cur.next = reverseHead.next; // 将当前节点的下一个节点链接到新链表中最前面的节点              reverseHead.next = cur; // 将当前节点链接到新链表              cur = next; // cur后移          }          head.next = reverseHead.next; // 将head.next指向reverseHead.next，实现反转      }  }

从尾到头打印单链表（Baidu）

public class Test{      /**       * 利用栈先进后出的特点，实现逆序打印的效果       * @param head       */      public static void reversePrint(HeroNode head){          if(head.next == null){              return;          }          Stack<HeroNode> stack = new Stack<>(); // 创建一个栈，将各个节点压入栈          HeroNode cur = head.next;          while (cur!=null){ // 循环将所有的链表的节点压入栈              stack.push(cur);              cur = cur.next;          }          while (stack.size()>0){              System.out.println(stack.pop()); // 出栈并打印          }      }  }