1、带环链表

给定一个链表，判断它是否有环。不要使用额外的空间

这道题的详解可见http://articles.leetcode.com/2010/09/detecting-loop-in-singly-linked-list.html

1 /** 2  * Definition for ListNode. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int val) { 7  *         this.val = val; 8  *         this.next = null; 9  *     }10  * }11  */ 12 public class Solution {13     /**14      * @param head: The first node of linked list.15      * @return: True if it has a cycle, or false16      */17     public boolean hasCycle(ListNode head) {  18         // write your code here19         ListNode fast,slow;20         fast = head;21         slow = head;22         while(fast!=null && (fast.next!=null)){23             slow = slow.next;24             fast = fast.next.next;25             if(slow == fast){26                 return true;27             }28         }29         return false;30     }31 }

2、寻找峰值

你给出一个整数数组(size为n)，其具有以下特点：

• 相邻位置的数字是不同的
• A[0] < A[1] 并且 A[n - 2] > A[n - 1]

假定P是峰值的位置则满足A[P] > A[P-1]且A[P] > A[P+1]，返回数组中任意一个峰值的位置。

这道题太简单了，有没有。。。。感觉是我目前在平台上刷到的最简单的题。。。

1 class Solution { 2     /** 3      * @param A: An integers array. 4      * @return: return any of peek positions. 5      */ 6     public int findPeak(int[] A) { 7         // write your code here 8         for ( int  i=1 ; i
     
      A[i-1]&&A[i]>A[i+1] ){10                 return i;11             }12         }13         return 0;14     }15 }
     

3、两个链表的交叉

样例

下列两个链表：

A:          a1 → a2                   ↘                     c1 → c2 → c3                   ↗            B:     b1 → b2 → b3

在节点 c1 开始交叉。

注意

• 如果两个链表没有交叉，返回null。
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。

挑战

需满足 O(n) 时间复杂度，且仅用 O(1) 内存。

1 public class Solution { 2     /** 3      * @param headA: the first list 4      * @param headB: the second list 5      * @return: a ListNode  6      */ 7     public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 8         // Write your code here 9         if(headA ==null || headB == null )   return null;10         int lenA = length(headA);//java中支持对数组调用.length直接计算长度，但是链表需要自己单独写。11         int lenB = length(headB);12         while(lenA > lenB ){13             headA = headA.next;14             lenA--;15         }16         while(lenA < lenB ){17             headB = headB.next;18             lenB--;19         }20         while(headA != headB ){21             headA = headA.next;22             headB = headB.next;23         }24         return headA;25     }  26     public int length(ListNode n){27         if(n==null) return 0;28         int length = 1;29         while(n.next != null ){30             length ++;31             n=n.next;32         }33         return length;34     }35 }