Java菜鸟的面试准备（一）

最近各种互联网公司内推、校招接踵而至，作为一名JAVA开发小菜鸟，使出了洪荒之力还有一种HOLD不住的赶脚，所以想在这里理理思路，闲话少说。 今天从链表开始 public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }

问题一：翻转链表 迭代：

public class ReverseLinkedList { public ListNode reverseList(ListNode head){ if (head==null||head.next==null) { return head; } ListNode pre = head; ListNode cur = head.next; pre.next=null; ListNode next =null; while (cur!=null) { next=cur.next; cur.next=pre; pre = cur; cur=next; } return pre; } }

递归：

public ListNode reverseList2(ListNode head){ if (head==null||head.next==null) { return head; } ListNode cur = head.next; ListNode newHead = reverseList2(cur); head.next=null; cur.next=head; return newHead; } 问题二：判断链表是否有环 public class LinkedListCycle { public boolean hasCycle(ListNode head) { if (head==null||head.next==null) { return false; } ListNode fast=head; ListNode slow =head; //fast==null fast==slow while (fast.next!=null&&fast.next.next!=null) { fast=fast.next.next; slow=slow.next; if (fast==slow) { return true; } } return false; } public ListNode detectCycle(ListNode head) { if (head==null||head.next==null) { return null; } ListNode fast=head; ListNode slow =head; //fast==null fast==slow while (fast.next!=null&&fast.next.next!=null) { fast=fast.next.next; slow=slow.next; if (fast==slow) { fast=head; while (fast!=slow) { fast=fast.next; slow=slow.next; } return fast; // return true; } } return null; } }

待续