// 非线程安全的数值序列生成器
public class UnsafeSequence {
    private int value;
    
    // 返回一个唯一的数值
    public int getNext() {
        return value++;
    }
}

// 线程安全的数值序列生成器
public class SafeSequence {
    private int value;
    
    // 返回一个唯一的数值
    public synchronized int getNext() {
        return value++;
    }
}

public class Solution {
	public static void main(String[] args) {
		char[] s = new char[]{'a', 'b', 'c', 'd', 'e', 'f'};
		leftShiftString(s, s.length, 3);
		System.out.println(s);
	}
	//移动首部m位字符到最后
	private static void leftShiftString(char[] s, int n, int m) {
		while (m > 0) {
			leftShiftOne(s, n);
			--m;
		}
	}
	//移动首位字符到最后
	private static void leftShiftOne(char[] s, int n) {
		char t = s[0];
		
		for (int i = 1; i < n; ++i) {
			s[i - 1] = s[i];
		}
		s[n - 1] = t;
	}
}

public class Solution2 {
	public static void main(String[] args) {
		char[] s = new char[]{'a', 'b', 'c', 'd', 'e', 'f'};
		leftRotateString(s, s.length, 3);
		System.out.println(s);
	}
	//字符串旋转
	private static void leftRotateString(char[] s, int n, int m) {
		m %= n; //若要左移动大于n位，那么与移动%n是等价的;
		reverseString(s, 0, m - 1);
		reverseString(s, m, n - 1);
		reverseString(s, 0, n - 1);
	}
	//字符串反转
	private static void reverseString(char[] s, int from, int to) {
		while (from < to) {
			char t = s[from];
			s[from++] = s[to];
			s[to--] = t;
		}
	}
}

public class Solution3 {
	public static void main(String[] args) {
		String str = "My name is luohuida!";
		char[] chs = leftRotateString(str.toCharArray(), str.length());
		System.out.println(chs);
	}
	//单词翻转
	private static char[] leftRotateString(char[] s, int n) {
		int i = 0;
		int j = 0;
		
		//先翻转每个单词
		for (; j < n; ++j) {
			if (j == n - 1 || s[j+1] == ' ') {
				reverseString(s, i, j);
				i = j + 2;
			}
		}
		
		reverseString(s, 0, n - 1);
		return s;
	}
	//字符串反转
	private static void reverseString(char[] s, int from, int to) {
		while (from < to) {
			char t = s[from];
			s[from++] = s[to];
			s[to--] = t;
		}
	}
}

/**
 * 图片加载类
 */
public class ImageLoader {
    // 图片缓存
    LruCache<String, Bitmap> mImageCache;
    // 线程池,线程数量为CPU的数量
    ExecutorService mExecutorService = Executors.newFixedThreadPool (Runtime.getRuntime().availableProcessors());
    public ImageLoader() {
        initImageCache();
    }
    private void initImageCache() {
            // 计算可使用的最大内存
        final int maxMemory = (int) (Runtime.getRuntime().maxMemory() / 1024);
            // 取四分之一的可用内存作为缓存
        final int cacheSize = maxMemory / 4;
        mImageCache = new LruCache<String, Bitmap>(cacheSize) {
            @Override
            protected int sizeOf(String key, Bitmap bitmap) {
                return bitmap.getRowBytes() * bitmap.getHeight() / 1024;
            }
        };
    }                   
    public  void displayImage(final String url, final ImageView imageView) {
        imageView.setTag(url);
        mExecutorService.submit(new Runnable() {
           @Override
            public  void run() {
              Bitmap bitmap = downloadImage(url);
                if (bitmap == null) {
                    return;
              }
                if (imageView.getTag().equals(url)) {
                    imageView.setImageBitmap(bitmap);
              }
                mImageCache.put(url, bitmap);
          }
       });
    }
    public  Bitmap downloadImage(String imageUrl) {
        Bitmap bitmap = null;
        try {
          URL url = newURL(imageUrl);
            final HttpURLConnection conn = (HttpURLConnection) 
                            url.openConnection();
            bitmap = BitmapFactory.decodeStream(conn.getInputStream());
            conn.disconnect();
        } catch (Exception e) {
            e.printStackTrace();
        }
        return bitmap;
    }
}

/**
 * 图片加载类
 */
public  class ImageLoader {
    // 图片缓存
    ImageCache mImageCache = new ImageCache() ;
    // 线程池,线程数量为CPU的数量
    ExecutorService mExecutorService = Executors.newFixedThreadPool (Runtime.getRuntime().availableProcessors());
 
    // 加载图片
    public  void displayImage(final String url, final ImageView imageView) {
        Bitmap bitmap = mImageCache.get(url);
        if (bitmap != null) {
            imageView.setImageBitmap(bitmap);
            return;
        }
        imageView.setTag(url);
        mExecutorService.submit(new Runnable() {
 
            @Override
            public void run() {
            Bitmap bitmap = downloadImage(url);
                if (bitmap == null) {
                    return;
                }
                if (imageView.getTag().equals(url)) {
                    imageView.setImageBitmap(bitmap);
                }
                mImageCache.put(url, bitmap);
            }
        });
     }
 
    public  Bitmap downloadImage(String imageUrl) {
        Bitmap bitmap = null;
        try {
           URL url = new URL(imageUrl);
            final HttpURLConnection conn = (HttpURLConnection) 
                        url.openConnection();
            bitmap = BitmapFactory.decodeStream(conn.getInputStream());
            conn.disconnect();
        } catch (Exception e) {
            e.printStackTrace();
        }
        return bitmap;
    }
}

public class ImageCache {
    // 图片LRU缓存
    LruCache<String, Bitmap> mImageCache;
    public ImageCache() {
        initImageCache();
    }
    private void initImageCache() {
         // 计算可使用的最大内存
        final int maxMemory = (int) (Runtime.getRuntime().maxMemory() / 1024);
        // 取四分之一的可用内存作为缓存
        final int cacheSize = maxMemory / 4;
        mImageCache = new LruCache<String, Bitmap>(cacheSize) {
            @Override
            protected int sizeOf(String key, Bitmap bitmap) {
                return bitmap.getRowBytes() * bitmap.getHeight() / 1024;
           }
        };
     }
    public void put(String url, Bitmap bitmap) {
        mImageCache.put(url, bitmap) ;
    }
    public Bitmap get(String url) {
        return mImageCache.get(url) ;
    }
}

public class DiskCache {
    // 为了简单起见临时写个路径,在开发中请避免这种写法 !
    static String cacheDir = "sdcard/cache/";
     // 从缓存中获取图片
    public Bitmap get(String url) {
        return BitmapFactory.decodeFile(cacheDir + url);
    }
    // 将图片缓存到内存中
    public  void  put(String url, Bitmap bmp) {
       FileOutputStream fileOutputStream = null;
        try {
            fileOutputStream = new FileOutputStream(cacheDir + url);
            bmp.compress(CompressFormat.PNG, 100, fileOutputStream);
      } catch (FileNotFoundException e) {
            e.printStackTrace();
      } final ly {
            if (fileOutputStream != null) {
                try {
                    fileOutputStream.close();
              } catch (IOException e) {
                    e.printStackTrace();
             }
          }
      }
    }
}

public class ImageLoader {
    // 内存缓存
    ImageCache mImageCache = new ImageCache();
    // SD卡缓存
    DiskCache mDiskCache = new DiskCache();
    // 是否使用SD卡缓存
    boolean isUseDiskCache = false;
    // 线程池,线程数量为CPU的数量
    ExecutorService mExecutorService = Executors.newFixedThreadPool (Runtime.getRuntime().availableProcessors());
    public  void displayImage(final String url, final ImageView imageView) {
        // 判断使用哪种缓存
       Bitmap bitmap = isUseDiskCache ? mDiskCache.get(url) 
                : mImageCache.get (url);
        if (bitmap != null) {
            imageView.setImageBitmap(bitmap);
            return;
       }
        // 没有缓存，则提交给线程池进行下载
    }
    public void useDiskCache(boolean useDiskCache) {
        isUseDiskCache = useDiskCache ;
    }
}

ImageLoader imageLoader = new ImageLoader() ;
 // 使用SD卡缓存
imageLoader.useDiskCache(true);
// 使用内存缓存
imageLoader.useDiskCache(false);

/**
 * 双缓存。获取图片时先从内存缓存中获取，如果内存中没有缓存该图片，再从SD卡中获取。
 *  缓存图片也是在内存和SD卡中都缓存一份
 */
public class DoubleCache {
    ImageCache mMemoryCache = new ImageCache();
    DiskCache mDiskCache = new DiskCache();
 
    // 先从内存缓存中获取图片，如果没有，再从SD卡中获取
    public   Bitmap get(String url) {
       Bitmap bitmap = mMemoryCache.get(url);
        if (bitmap == null) {
            bitmap = mDiskCache.get(url);
       }
        return  bitmap;
    }
 
    // 将图片缓存到内存和SD卡中
    public void put(String url, Bitmap bmp) {
        mMemoryCache.put(url, bmp);
        mDiskCache.put(url, bmp);
   }
}

public class ImageLoader {
    // 内存缓存
    ImageCache mImageCache = new ImageCache();
    // SD卡缓存
    DiskCache mDiskCache = new DiskCache();
    // 双缓存
    DoubleCache mDoubleCache = new DoubleCache() ;
    // 使用SD卡缓存
    boolean isUseDiskCache = false;
    // 使用双缓存
    boolean isUseDoubleCache = false;
    // 线程池,线程数量为CPU的数量
    ExecutorService mExecutorService = Executors.newFixedThreadPool (Runtime.getRuntime().availableProcessors());
 
 
    public void displayImage(final String url, final ImageView imageView) {
        Bitmap bmp = null;
         if (isUseDoubleCache) {
            bmp = mDoubleCache.get(url);
        } else if (isUseDiskCache) {
            bmp = mDiskCache.get(url);
        } else {
            bmp = mImageCache.get(url);
        }
 
         if ( bmp != null ) {
            imageView.setImageBitmap(bmp);
        }
        // 没有缓存，则提交给线程池进行异步下载图片
    }
 
    public void useDiskCache(boolean useDiskCache) {
        isUseDiskCache = useDiskCache ;
    }
 
    public void useDoubleCache(boolean useDoubleCache) {
        isUseDoubleCache = useDoubleCache ;
    }
}

public class ImageLoader {
    // 图片缓存
    ImageCache mImageCache = new MemoryCache();
    // 线程池,线程数量为CPU的数量
    ExecutorService mExecutorService = Executors.newFixedThreadPool (Runtime.getRuntime().availableProcessors());
 
    // 注入缓存实现
    public void setImageCache(ImageCache cache) {
        mImageCache = cache;
    }
 
    public void displayImage(String imageUrl, ImageView imageView) {
        Bitmap bitmap = mImageCache.get(imageUrl);
        if (bitmap != null) {
            imageView.setImageBitmap(bitmap);
            return;
        }
        // 图片没缓存，提交到线程池中下载图片
        submitLoadRequest(imageUrl, imageView);
    }
 
    private void submitLoadRequest(final String imageUrl,
             final ImageView imageView) {
        imageView.setTag(imageUrl);
        mExecutorService.submit(new Runnable() {
 
            @Override
            public  void run() {
              Bitmap bitmap = downloadImage(imageUrl);
                if (bitmap == null) {
                    return;
             }
               if (imageView.getTag().equals(imageUrl)) {
                    imageView.setImageBitmap(bitmap);
             }
                mImageCache.put(imageUrl, bitmap);
         }
      });
    }
 
    public  Bitmap downloadImage(String imageUrl) {
       Bitmap bitmap = null;
        try {
           URL url = new URL(imageUrl);
            final HttpURLConnection conn = (HttpURLConnection) 
                        url.openConnection();
            bitmap = BitmapFactory.decodeStream(conn.getInputStream());
            conn.disconnect();
        } catch (Exception e) {
              e.printStackTrace();
        }
 
        return bitmap;
    }
}

public interface ImageCache {
    public Bitmap get(String url);
    public void put(String url, Bitmap bmp);
}

// 内存缓存MemoryCache类
public class MemoryCache implements ImageCache {
    private LruCache<String, Bitmap> mMemeryCache;
 
    public MemoryCache() {
        // 初始化LRU缓存
    }
 
     @Override
    public Bitmap get(String url) {
        return mMemeryCache.get(url);
    }
 
    @Override
    public void put(String url, Bitmap bmp) {
        mMemeryCache.put(url, bmp);
    }
}
 
// SD卡缓存DiskCache类
public  class  DiskCache implements ImageCache {
    @Override
    public Bitmap get(String url) {
        return null/* 从本地文件中获取该图片 */;
    }
 
    @Override
    public void put(String url, Bitmap bmp) {
        // 将Bitmap写入文件中
    }
}
 
// 双缓存DoubleCache类
public class DoubleCache implements ImageCache{
    ImageCache mMemoryCache = new MemoryCache();
    ImageCache mDiskCache = new DiskCache();
 
    // 先从内存缓存中获取图片，如果没有，再从SD卡中获取
    public Bitmap get(String url) {
       Bitmap bitmap = mMemoryCache.get(url);
        if (bitmap == null) {
            bitmap = mDiskCache.get(url);
       }
        return bitmap;
     }
 
    // 将图片缓存到内存和SD卡中
    public void put(String url, Bitmap bmp) {
        mMemoryCache.put(url, bmp);
        mDiskCache.put(url, bmp);
    }
}

ImageLoader imageLoader = new ImageLoader() ;
        // 使用内存缓存
imageLoader.setImageCache(new MemoryCache());
        // 使用SD卡缓存
imageLoader.setImageCache(new DiskCache());
        // 使用双缓存
imageLoader.setImageCache(new DoubleCache());
        // 使用自定义的图片缓存实现
imageLoader.setImageCache(new ImageCache() {
            @Override
        public void put(String url, Bitmap bmp) {
            // 缓存图片
       }
            @Override
        public Bitmap get(String url) {
            return null/*从缓存中获取图片*/;
       }
    });

// 窗口类
public class Window {
    public void show(View child){
        child.draw();
    }
}
// 建立视图抽象，测量视图的宽高为公用代码，绘制交给具体的子类
public abstract class  View {
    public abstract void  draw() ;
    public void  measure(int width, int height){
        // 测量视图大小
    }
}
// 按钮类的具体实现
public class Button extends View {
    public void draw(){
        // 绘制按钮
    }
}
// TextView的具体实现
public class TextView extends View {
    public void draw(){
        // 绘制文本
    }
}

public class ImageLoader {
    // 内存缓存 ( 直接依赖于细节 )
    MemoryCache mMemoryCache = new MemoryCache();
     // 加载图片到ImageView中
    public void displayImage(String url, ImageView imageView) {
       Bitmap bmp = mMemoryCache.get(url);
        if (bmp == null) {
            downloadImage(url, imageView);
       } else {
            imageView.setImageBitmap(bmp);
       }
    }
    public void setImageCache(MemoryCache cache) {
        mCache = cache ;
    }
    // 代码省略
}

public class ImageLoader {
    // 双缓存 ( 直接依赖于细节 )
    DoubleCache mCache = new DoubleCache();
    // 加载图片到ImageView中
    public void displayImage(String url, ImageView imageView) {
       Bitmap bmp = mCache.get(url);
        if (bmp == null) {
          // 异步下载图片
            downloadImageAsync(url, imageView);
       } else {
            imageView.setImageBitmap(bmp);
       }
    }
    public void setImageCache(DoubleCache cache) {
         mCache = cache ;
    }
    // 代码省略
}

public interface ImageCache {
    public Bitmap get(String url);
    public void put(String url, Bitmap bmp);
}

public class ImageLoader {
    // 图片缓存类，依赖于抽象，并且有一个默认的实现
    ImageCache mCache = new MemoryCache();
    // 加载图片
    public void displayImage(String url, ImageView imageView) {
       Bitmap bmp = mCache.get(url);
        if (bmp == null) {
        // 异步加载图片
            downloadImageAsync(url, imageView);
       } else {
            imageView.setImageBitmap(bmp);
       }
    }
    /**
     * 设置缓存策略,依赖于抽象
     */
    public void setImageCache(ImageCache cache) {
        mCache = cache;
    }
    // 代码省略
}

// 将图片缓存到内存中
public void put(String url, Bitmap bmp) {
    FileOutputStream fileOutputStream = null;
    try {
        fileOutputStream = new FileOutputStream(cacheDir + url);
        bmp.compress(CompressFormat.PNG, 100, fileOutputStream);
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    } finally {
        if (fileOutputStream != null) {
            try {
                fileOutputStream.close();
          } catch (IOException e) {
                e.printStackTrace();
          }
       } // end if
    } // end if finally
}

public final class CloseUtils {
    Private CloseUtils() { }
    /**
     * 关闭Closeable对象
     * @param closeable
     */
    public static void closeQuietly(Closeable closeable) {
        if (null != closeable) {
            try {
                closeable.close();
        } catch (IOException e) {
                e.printStackTrace();
        }
       }
    }
}

public void put(String url, Bitmap bmp) {
    FileOutputStream fileOutputStream = null;
    try {
        fileOutputStream = new FileOutputStream(cacheDir + url);
        bmp.compress(CompressFormat.PNG, 100, fileOutputStream);
   } catch (FileNotFoundException e) {
        e.printStackTrace();
   } final ly {
        CloseUtils.closeQuietly(fileOutputStream);
   }
}

/**
 * 房间
 */
public class Room {
    public float area;
    public float price;
    public Room(float  area, float  price) {
        this.area = area;
        this.price = price;
    }
    @Override
    public String toString() {
        return "Room [area=" + area + ", price=" + price + "]";
    }
}
/**
 * 中介
 */
public class Mediator {
    List<Room> mRooms = new ArrayList<Room>();
    public Mediator() {
        for (inti = 0; i < 5; i++) {
            mRooms.add(new Room(14 + i, (14 + i) * 150));
       }
   }
    public List<Room>getAllRooms() {
        return mRooms;
   }
}
/**
 * 租户
 */
public class Tenant {
    public float roomArea;
    public float roomPrice;
    public static final float diffPrice = 100.0001f;
    public static final float diffArea = 0.00001f;
    public void rentRoom(Mediator mediator) {
        List<Room>rooms = mediator.getAllRooms();
        for (Room room : rooms) {
            if (isSuitable(room)) {
             System.out.println("租到房间啦! " + room);
                break;
          }
       }
    }
    private boolean isSuitable(Room room) {
        return Math.abs(room.price - roomPrice) < diffPrice
                &&Math.abs(room.area - roomArea) < diffArea;
   }
}

/**
 * 中介
 */
public class Mediator {
    List<Room> mRooms = new ArrayList<Room>();
    public Mediator() {
        for (inti = 0; i < 5; i++) {
            mRooms.add(new Room(14 + i, (14 + i) * 150));
       }
    }
    public Room rentOut(float  area, float  price) {
        for (Room room : mRooms) {
            if (isSuitable(area, price, room)) {
                return  room;
          }
       }
        return null;
    }
    private boolean isSuitable(float area, float price, Room room) {
        return Math.abs(room.price - price) < Tenant.diffPrice
            && Math.abs(room.area - area) < Tenant.diffPrice;
    }
}
/**
 * 租户
 */
public class Tenant {
    public float roomArea;
    public float roomPrice;
    public static final float diffPrice = 100.0001f;
    public static final float diffArea = 0.00001f;
    public void rentRoom(Mediator mediator) {
        System.out.println("租到房啦 " + mediator.rentOut(roomArea, roomPrice));
     }
}

public void put(String url, Bitmap value) {
    DiskLruCache.Editor editor = null;
    try {
       // 如果没有找到对应的缓存，则准备从网络上请求数据，并写入缓存
        editor = mDiskLruCache.edit(url);
        if (editor != null) {
                OutputStream outputStream = editor.newOutputStream(0);
            if (writeBitmapToDisk(value, outputStream)) {
              // 写入disk缓存
                editor.commit();
          } else {
                editor.abort();
          }
            CloseUtils.closeQuietly(outputStream);
       }
    } catch (IOException e) {
         e.printStackTrace();
    }
}

@Override
public  void put(String url, Bitmap bmp) {
    // 将Bitmap写入文件中
    FileOutputStream fos = null;
    try {
       // 构建图片的存储路径 ( 省略了对url取md5)
        fos = new FileOutputStream("sdcard/cache/" + imageUrl2MD5(url));
        bmp.compress(CompressFormat.JPEG, 100, fos);
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    } finally {
        if ( fos != null ) {
            try {
                fos.close();
          } catch (IOException e) {
                e.printStackTrace();
          }
       }
    } // end if finally
}

// 反转单链表
public static Node traversingReverse(Node head) {
	Node result = null;
	Node temp = null;
	// 头反转法：把当前节点拿过来作为已经翻转结果的表头
	while (head != null) {
		temp = head.next; // 保存下一个节点
		head.next = result; // 当前节点放在结果的开头
		result = head; // 当前节点的头
		head = temp; // head指向下一个节点
	}
	return result;
}

// O(1)复杂度删除某个节点
public static void lazyDelete(Node now) {
    if(now.next != null) { // ①非尾节点
        now.value = now.next.value; // 复制后驱节点的值
        now.next = now.next.next; // “删除”后驱节点
    }  else{ // ②尾节点，行不通
        return;
    }
}

// 求单链表倒数第k个节点
public static Node getKNode(Node head, int k) {
    Node fast = head;
    Node slow = head;
    
    int i = 0;
    for(; i < k && fast != null; i++) {
        fast = fast.next;
    }
    
    if(i != k) {
        System.out.println(k + "位置超出链表长度");
    }
    
    while(fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    return slow;
}

// 求链表的中间节点
public static Node getMiddleNode(Node head) {
    if (head == null) {
        return null;
    }
    
    Node fast = head;
    Node slow = head;
    
    // ①如果fast==null的话，说明是偶数个；而fast.next==null的话，说明是奇数个
    // ①条件返回的是偶数情况中的后者，如果要返回前者，可用下面判断条件：
    // while (fast != null && fast.next != null && fast.next.next != null)
    while (fast != null && fast.next != null) { // ①
        fast = fast.next.next; // 快指针走2步
        slow = slow.next; // 慢指针走1步
    }
    
    return slow;
}

// 利用HashMap判断是否有环
public static boolean hasCircle(Node head) {
    Set<Node> set = new HashSet<>();
    while (head != null) {
    	if(getFromSet(set, head) != null) {
    		return true;
    	}
    	
    	set.add(head);
    	head = head.next;
    }
    return false;
}
// 由于Set没有提供get()方法，所以自己实现一个
// 缘何Set不提供get()？？？
public static Node getFromSet(Set<Node> set, Node node) {
	Iterator it = set.iterator();
	Node tmp;
	while(it.hasNext()) {
		tmp = (Node)it.next();
		if(tmp == node) {
			return tmp;
		}
	}
	return null;
}

// 利用快慢指针判断链表是否有环
public static boolean hasCircle(Node head) {
    Node fast = head;
    Node slow = head;
    
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        
        if (fast == slow) {
            return true;
        }
    }
    
    return false;
}

// 使用快慢指针求环起点
public static Node listCircleStart(Node head) {
    // 空链或者单节点，不存在环
    if(head == null || head.next == null) {
        return null;
    }
    
    Node fast = head;
    Node slow = head;
    
    do {
        if (fast == null || fast.next == null) { // 无环
            return null;
        }
        
        fast = fast.next.next; // 走2步
        slow = slow.next; // 走1步
    } while (fast != slow) // 直到fast和slow相遇
    
    fast = head; // 重新拉回链表起点
    while (fast != slow) { // 相遇即为环起点
        fast = fast.next; // 走1步
        slow = slow.next; // 走1步
    }
    
    return fast;
}

// 使用快慢指针求环长度
public static int listCircleLength(Node head) {
    Node cicleStart = listCircleStart(head); // 先利用上面的方法求出环起点
    
    if(cicleStart == null) {
        return 0;
    }
    
    Node tmp = cicleStart.next;
    int counter = 1;
    while (tmp != cicleStart) { // 重走一遍，直到回到环起点
        counter++;
        tmp = tmp.next;
    }
    
    return counter;
}

// 利用Set求2链表交点
public static Node getCrossNode(Node headA, Node headB) {
    Set<Node> set = new Hash<>();
    
    // 把a链全部放入Set中
    while (headA != null) {
        set.add(headA);
        headA = headA.next;
    }
    
    // 遍历b链
    while (headB != null) {
        if(set.getFromSet(set, headB) != null) { // 相交
            return headB;
        }
    }
    
    return null;
}
public static Node getFromSet(Set<Node> set, Node node) {
	Iterator it = set.iterator();
	Node tmp;
	while(it.hasNext()) {
		tmp = (Node)it.next();
		if(tmp == node) {
			return tmp;
		}
	}
	return null;
}

// 链长先走求2链交点
public static Node getCrossNode(Node headA, Node headB) {
    int x = 0; // 链a长度
    int y = 0; // 链b长度
    
    Node tmp = headA; // 因为后续还要用到headA，所以用临时变量来遍历
    while(tmp != null) {
        x++;
        tmp = tmp.next;
    }
    tmp = headB;
    while(tmp != null) {
        y++;
        tmp = tmp.next;
    }
    
    int k; // 链长度差
    if (x - y > 0) { // a链长
        k = x - y;
        
        // a链走k步
        for (int i = 0; i < k; i++) {
            headA = headA.next;
        }
    } else {
        k = y - x;
        
        // b链走k步
        for (int i = 0; i < k; i++) {
            headB = headB.next;
        }
    }
    
    // 这时候，headA指向的子链和headB指向的子链长度一样，一起走
    while (headA != null) { // 这里不需要判断headB，因为headA和headB肯定同时为null
        if(headA == headB) { // 相遇的节点是交点
            return headA
        }
        
        headA = headA.next;
        headB = headB.next;
    }
    
    return null;
}

// 利用map实现带random指针的链表复制
public static NodeWithRandom copyWithRandom (NodeWithRandom h) {
	NodeWithRandom newNode = null;
	Map<NodeWithRandom, NodeWithRandom> map = new HashMap<>();
	map.put(null, null); // 解决random指向null的情况
	// 先用常规方法复制链表
	NodeWithRandom tmp1 = h;
	NodeWithRandom h2 = null;
	while (tmp1 != null) {
		if(newNode == null) { // 表头
			newNode = new NodeWithRandom(tmp1.value);
			h2 = newNode;
		} else {
			newNode.next = new NodeWithRandom(tmp1.value);
			newNode = newNode.next;
		}
		map.put(tmp1, newNode); // 旧地址到新地址的映射
		tmp1 = tmp1.next;
	}
	// 再两个链表同时走复制random，a'.random = map[a.random]
	tmp1 = h;
	NodeWithRandom tmp2 = h2;
	while (tmp1 != null) {
		tmp2.random = map.get(tmp1.random); // 利用map的映射，将新链表的random指针指向新节点
		tmp1 = tmp1.next;
		tmp2 = tmp2.next;
	}
	return h2;
}
// 带random的节点
class NodeWithRandom {
	public int value;
	public NodeWithRandom next;
	public NodeWithRandom random;
	public NodeWithRandom (int value) {
		this.value = value;
		this.next = null;
		this.random = null;
	}
}

// "副本"方式复制带随机指针链表
public static NodeWithRandom copyRandomList (NodeWithRandom head) {
	if (head == null) {
		return null;
	}
	// 在每个节点后创建副本，拉成链
	NodeWithRandom now = head; 
	while (now != null) {
		NodeWithRandom copy = new NodeWithRandom(now.value);
		copy.next = now.next;
		now.next = copy;
		now = copy.next;
	}
	// 复制random
	for (now = head; now != null; now = now.next.next) {
		now.next.random = now.random == null ? null : now.random.next; // 新节点的random=旧节点random的next
	}
	// 奇数项为旧节点，偶数项为新节点
	// 提取出偶数项就是所求
	NodeWithRandom h = head.next; // 新链头部
	NodeWithRandom t = h; // 遍历游标
	NodeWithRandom tail = head;
	for (;;) {
		tail.next = t.next; // 重连旧节点
		tail = tail.next; // 移向下一个旧节点
		if(tail == null) {
			break;
		}
		t.next = tail.next; // 连接新节点
		t = t.next; // 移向下一个新节点
	} 
	return h;
}

// 链表的partition过程
public static Node(Node head, int x) {
    Node h1 = null; // 小子链头部
    Node h2 = null; // 大子链头部
    Node t1 = null; // 小子链尾部
    Node t2 = null; // 大子链尾部
    
    for (; head != null; head = head.next) {
        if (head.val < x) { // 比x小
            if (h1 = null) { // 头部
                h1 = head;
                t1 = head;
            } else {
                t1.next = head;
                t1 = t1.next;
            }
        } else {
            if (h2 == null) {
                h2 = head;
                t2 = head;
            } else {
                t2.next = head;
                t2 = t2.next;
            }
        }
    }
    
    if (t2 != null) { // 大子链有节点
        t2.next = null;
    }
    if(t1 != null) { // 小子链有节点
        t1.next = h2;
    }
        
    return h1 != null ? h1 : h2;    
}

// 建立链表
private static Node buildList(int size) {
	Node first = null;
	Node newNode = null;
	// 头插入法
	for (int i = 0; i < size; i++) {
		newNode = new Node(i);
		newNode.next = first;
		first = newNode;
	}
    return first;
}

private static Node buildListLast(int size) {
	Node first = null;
	Node last = null;
	Node now = null;
	// 后插法
	for(int i = 0; i < size; i++) {
		now = new Node(i);
		now.next = null;
		if(first == null) {				
			first = now;
		} else {
			last.next = now;				
		}
		last = now;
	}
	return first;
}

// 将新元素插入到第index个节点之后。index从1开始，index = 0表示插入到第一个节点之前
private static Node insert(Node first, Node newNode, int index) {
	// ①如果链表为空，或者插入的索引为0，则插入到前端
	if(first == null || index == 0) {
		newNode.next = first;
		first = newNode;
	} else {
		Node current = first;
		for(int k = 1; k < index; k++) {
			if(current == null) {
				break;
			} else {
				current = current.next;
			}
		}
		if(current == null) {
			System.out.println("无效的插入位置");
		} else { //  ②插入中间或尾部
			newNode.next = current.next;
			current.next = newNode;
		}
	}
	return first;
}

// 将链表的第index个元素删除，index从1开始
private static Node delete(Node first, int index) {
	Node del = null;
	Node current = null;
	if(index < 1) { // ①删除头结点
		del = first;
		first = first.next;
		del = null; // 让GC回收
	} else {
		current = first;
		for(int k = 1; k < index - 1; k++) {
			if(current == null) {
				break;
			} else {
				current = current.next;
			}
		}
		if(current == null || current.next == null) {
			System.out.println("无效的删除位置");
		} else { // ②删除中间节点或尾部节点
			del = current.next;
			current.next = del.next;
			del = null;
		}
	}
	return first;
}

// 遍历链表
private static void traveling(Node first) {
	Node h = first;   
    while (h != null) {   
        System.out.print(h.value + " ");   
        h = h.next;   
    }   
}

class Singleton {
    // 类加载的时候就会初始化，这个过程有且仅有一次
    private static final Singleton instance = new Singleton();
    // 私有的构造方法
    private Singleton() {}
    // 对外提供唯一的Singleton实例
    public static Singleton getInstance() throws InterruptedException {
        return instance;
    }
}

class Singleton {
    private static Singleton instance;
    private Singleton() {}
    public static Singleton getInstance() throws InterruptedException {
        if (instance == null) { // a
            // 为了加大出现线程问题的概率，我们在这里休眠1秒
            Thread.sleep(1000);
            instance = new Singleton(); // b
        }
        return instance;
    }
}

class Singleton {
    private static Singleton instance;
    private Singleton() {}
    public static synchronized Singleton getInstance() throws InterruptedException {
        if (instance == null) { // a
            // 为了出现线程问题，我们在这里休眠1000毫秒。(当然这里并不出现线程安全问题)
            Thread.sleep(1000);
            instance = new Singleton(); // b：这里不会释放掉对象锁，所以其他线程无法进入
        }
        return instance;
    }
}

class Singleton {
    private static Singleton instance;// private static volatile Singleton instance;
    private Singleton() {}
    public static Singleton getInstance() throws InterruptedException {
        if(instance == null){// 第一次校验
            synchronized (Singleton.class){// 锁
                if(instance == null){// 第二次校验
                    Thread.sleep(1000);
                    instance = new Singleton();// a：可加赋值的内存屏障
                }
            }
        }
        return instance;
    }
}

class Singleton {
    private static class SingletonHolder{
        private static final Singleton INSTANCE = new Singleton();
    }
    private Singleton(){}
    public static final Singleton getInstance(){
        return SingletonHolder.INSTANCE;
    }
}

public enum Singleton {
    INSTANCE;
}

public abstract class Enum<E extends Enum<E>>
        implements Comparable<E>, Serializable

private Enum<?> readEnum(boolean unshared) throws IOException {
       ...
        String name = readString(false);
        Enum<?> result = null;
        Class<?> cl = desc.forClass();
        if (cl != null) {
            try {
                @SuppressWarnings("unchecked")
                Enum<?> en = Enum.valueOf((Class)cl, name);
                result = en;
            } catch (IllegalArgumentException ex) {
                throw (IOException) new InvalidObjectException(
                    "enum constant " + name + " does not exist in " +
                    cl).initCause(ex);
            }
            if (!unshared) {
                handles.setObject(enumHandle, result);
            }
        }
        handles.finish(enumHandle);
        passHandle = enumHandle;
        return result;
    }

public static <T extends Enum<T>> T valueOf(Class<T> enumType,
                                                String name) {
        T result = enumType.enumConstantDirectory().get(name);
        if (result != null)
            return result;
        if (name == null)
            throw new NullPointerException("Name is null");
        throw new IllegalArgumentException(
            "No enum constant " + enumType.getCanonicalName() + "." + name);
    }

Map<String, T> enumConstantDirectory() {
    if (enumConstantDirectory == null) {
        T[] universe = getEnumConstantsShared();
        if (universe == null)
            throw new IllegalArgumentException(
                getName() + " is not an enum type");
        Map<String, T> m = new HashMap<>(2 * universe.length);
        for (T constant : universe)
            m.put(((Enum<?>)constant).name(), constant);
        enumConstantDirectory = m;
    }
    return enumConstantDirectory;
}

 public static void main(String[] args) throws Exception {
    // 常规方法获取实例
    Singleton commonSingleton = Singleton.getInstance();
    // 通过反射获取实例
    Constructor constructor = Singleton.class.getDeclaredConstructor(String.class, int.class);
    constructor.setAccessible(true);
    Singleton reflectionSingleton = (Singleton) constructor.newInstance();
    // 这里会输出： false，证明两个实例不一样，单例模式被破坏了
    System.out.println(reflectionSingleton == commonSingleton);
}

Exception in thread "main" java.lang.IllegalArgumentException: Cannot reflectively create enum objects
    at java.lang.reflect.Constructor.newInstance(Constructor.java:417)
    at com.github.archerda.designpattern.singleton.destory.reflection.BreakingSingleton.main(BreakingSingleton.java:23)

@CallerSensitive
   public T newInstance(Object ... initargs)
       throws InstantiationException, IllegalAccessException,
              IllegalArgumentException, InvocationTargetException
   {
       if (!override) {
           if (!Reflection.quickCheckMemberAccess(clazz, modifiers)) {
               Class<?> caller = Reflection.getCallerClass();
               checkAccess(caller, clazz, null, modifiers);
           }
       }
       if ((clazz.getModifiers() & Modifier.ENUM) != 0)
           throw new IllegalArgumentException("Cannot reflectively create enum objects");
       ConstructorAccessor ca = constructorAccessor;   // read volatile
       if (ca == null) {
           ca = acquireConstructorAccessor();
       }
       @SuppressWarnings("unchecked")
       T inst = (T) ca.newInstance(initargs);
       return inst;
   }

public class Runtime {
    private static Runtime currentRuntime = new Runtime();
    public static Runtime getRuntime() {
        return currentRuntime;
    }
    private Runtime() {}
    ....
}

//  第一个Spring Bean容器
ApplicationContext context1 = new FileSystemXmlApplicationContext("classpath:/ApplicationContext.xml");
Person person1 = context1.getBean("person", Person.class);
//  第二个Spring Bean容器
ApplicationContext context2 = new FileSystemXmlApplicationContext("classpath:/ApplicationContext.xml");
Person person2 = context2.getBean("person", Person.class);
//  这里绝对不会相等，因为创建了多个实例
System.out.println(person1 == person2);