单向链表面试题(新浪百度腾讯)

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

遍历数组,通过length++ 得到有效节点的个数

//返回单向链表的有效节点 public static int getLength(Node head){ int length=0; //遍历数组 Node temp=head.next; while (true){ if (temp!=null){ length++; }else { break; } temp=temp.next; } return length; }

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

/** *查找单链表中的倒数第 k 个结点 【新浪面试题】 */ public static Node findNodeByk(int k,LinkedLiset linkedLiset){ //找倒数第k个节点就是找length-k个节点的next //先遍历数组获取有效节点数 Node head1= getHead(linkedLiset);//获取头结点 int lengeth = getLength(head1);//获取有效节点数 if (head1.next==null){//判断链表是否为空 System.out.println("链表为空"); return null; } if (k<0|k>lengeth){//判断k的值是否合法 System.out.println("k非法"); } Node cur=head1; //通过循环找到倒数第k个节点的前一个节点cur for (int i = 0;i<lengeth-k;i++){ cur=cur.next; } return cur.next;//返回第k个节点 }

单链表的反转【腾讯面试题，有点难】

* 思路 * 先创建一个新的头节点 * 遍历原链表,每取出一个节点,就把其放在新链表的最前面 */ public void fanzhuan(){ Node node=new Node(null,null,0);//创建的新链表的头结点 if (head.next==null|head.next.next==null){ return; } Node temp=head.next;//创建辅助节点 Node next=null;//创建变量保存当前节点下个节点 //遍历原链表 while (true){ if (temp==null){ break;//表示已经遍历到链表最后一个 } next=temp.next;//将取出节点的下一个节点保存 temp.next=node.next;//将取出节点下下一个节点指向链表的最前端 node.next=temp;//再将取出的节点放在新链表的最前端 temp=next; } head.next=node.next;//将原链表的第一个节点 换成新链表的第一个节点 }

) 从尾到头打印单链表 【百度，要求方式 1：反向遍历 。 方式 2：Stack 栈】

方式1 会破坏原链表 不建议 方式2:创建Stack对象通过add 和pop方法就可以实现 不做过多讲解