目录
1 左神部分集锦
2 Leetcode前150题
3 牛客网剑指offer
4 JavaG
5 题目中的细节处理
1 左神部分集锦
1.1 Code01_FindNumber_B_In_A
在有序数组A中，找到B中（不）存在的数。
public class Code01_FindNumber_B_In_A {
// 生成随机数组
public static int[] generateRandomArray(int maxSize, int MaxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((MaxValue + 1) * Math.random()) - (int) (MaxValue * Math.random());
}
return arr;
}
// 二分法
public static int[] binary(int[] A, int[] B) {
if (A == null || B == null) {
return null;
}
int[] help = new int[B.length];
for (int i = 0; i < B.length; i++) {
int l = 0;
int r = A.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (B[i] < A[mid]) {
r = mid - 1;
} else if (B[i] > A[mid]) {
l = mid + 1;
} else {
break;
}
}
if (l > r) {
help[i] = B[i];// 不在A中数
}
}
return help;
}
// 类似外排的方法
public static List<Integer> waipai(int[] A, int[] B) {
Arrays.sort(B);
List<Integer> help = new ArrayList<>();
int p1 = 0;
int p2 = 0;
while (p1 < A.length && p2 < B.length) {
if (A[p1] < B[p2]) {
p1++;
} else if (A[p1] > B[p2]) {
p2++;
} else {
help.add(B[p2]); //在A中的数
p1++;
p2++;
}
}
return help;
}
public static void main(String[] args) {
int AMaxSize = 10;
int BMaxSize = 10;
int MaxValue = 100;
int[] A = generateRandomArray(AMaxSize, MaxValue);
int[] B = generateRandomArray(BMaxSize, MaxValue);
// int[] A = { 1, 2, 3, 4, 5 };
// int[] B = { 1, 6, 3 ,5};
int[] res = binary(A, B);
// List<Integer> list = waipai(A, B);
System.out.println(Arrays.toString(A));
System.out.println(Arrays.toString(B));
System.out.println(Arrays.toString(res));
// for (Integer integer : list) {
// System.out.print(integer + " ");
// }
}
}
1.2 Code02_BubbleSort
public class Code02_BubbleSort {
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = arr.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int)((maxSize + 1) * Math.random())];
for(int i =0; i < arr.length; i++) {
arr[i] = (int)((maxValue + 1)*Math.random()) - (int)(maxValue * Math.random());
}
return arr;
}
public static void main(String[] args) {
int maxSize = 20;
int maxValue = 100;
int[] arr = generateRandomArray(maxSize, maxValue);
System.out.println(Arrays.toString(arr));
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
}
1.3 Code03_InsertSort
public class Code03_InsertSort {
public static void insertSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j > -1; j--) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static void main(String[] args) {
int[] A = {4,1,2,7,40,35,51};
System.out.println(Arrays.toString(A));
insertSort(A);
System.out.println(Arrays.toString(A));
}
}
1.4 Code04_SelectSort
public class Code04_SelectSort {
public static void selectSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr, i, minIndex);
}
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int)((maxSize+1)*Math.random())];
for(int i=0;i<arr.length;i++) {
arr[i] = (int)((maxValue+1)*Math.random())-(int)(maxValue * Math.random());
}
return arr;
}
public static void main(String[] args) {
int[] arr = generateRandomArray(10, 50);
System.out.println(Arrays.toString(arr));
selectSort(arr);
System.out.println(Arrays.toString(arr));
}
}
1.5 Code05_MergeSort
public class Code05_MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
private static void mergeSort(int[] arr, int l, int r) {
if (l == r) {
return;
}
int mid = l + (r - l) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
private static void merge(int[] arr, int l, int mid, int r) {
int[] help = new int[r - l + 1];
int index = 0;
int p1 = l;
int p2 = mid + 1;
while (p1 <= mid && p2 <= r) {
help[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid) {
help[index++] = arr[p1++];
}
while (p2 <= r) {
help[index++] = arr[p2++];
}
for (int i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = new int[] { 2, 5, 1, 3, 6, 2, 1 };
mergeSort(arr);
System.out.println(Arrays.toString(arr));
}
}
1.6 Code06_SmallNumberSum
小和问题：在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。
public class Code06_SmallNumberSum {
public static int getSum(int[] arr) {
if(arr==null || arr.length < 2) {
return 0;
}
return mergeSort(arr, 0, arr.length - 1);
}
private static int mergeSort(int[] arr, int l, int r) {
if(l == r) {
return 0;
}
int mid = l + (r - l) / 2;
return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
}
private static int merge(int[] arr, int l, int mid, int r) {
int sum = 0;
int[] help = new int[r - l + 1];
int index = 0;
int p1 = l;
int p2 = mid + 1;
while(p1 <= mid && p2 <= r) {
sum += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
help[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while(p1 <= mid) {
help[index++] = arr[p1];
}
while(p2 <= r) {
help[index++] = arr[p2++];
}
for(int i =0 ; i < help.length; i++) {
arr[l + i] = help[i];
}
return sum;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = new int[]{1,3,4,2,5};
System.out.print(getSum(arr));
}
}
// output:16
1.7 Code07_QuickSort
随机快排
public class Code07_QuickSort {
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int l, int r) {
if (l < r) {
swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
int[] p = partition(arr, l, r);
quickSort(arr, l, p[0] - 1);
quickSort(arr, p[1] + 1, r);
}
}
private static int[] partition(int[] arr, int l, int r) {
int less = l-1;
int more = r;
while (l < more) {
if (arr[l] < arr[r]) {
swap(arr, l++, ++less);
} else if (arr[l] > arr[r]) {
swap(arr, l, --more);
} else {
l++;
}
}
swap(arr, more, r);
return new int[] { less + 1, more };
}
public static int[] generateRandomArray(int maxsize, int maxvalue) {
int[] arr = new int[(int) ((maxsize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxvalue + 1) * Math.random()) - (int) (maxvalue * Math.random());
}
return arr;
}
private static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = generateRandomArray(20, 20);
System.out.println(Arrays.toString(arr));
quickSort(arr);
System.out.println(Arrays.toString(arr));
}
}
1.8 Code08_HeapSort
public class Code08_HeapSort {
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
//���������
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int size = arr.length - 1;
swap(arr, size, 0);
while(size > 0) {
heapIfy(arr, 0, size);
swap(arr, --size, 0);
}
}
// ��������β�������ϱȽ�
private static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
// �Ѷ�Ԫ�ظı䣬���±Ƚ�
public static void heapIfy(int[] arr, int index, int size) {
int left = index * 2 + 1;
while(left < size) {
int largest = left + 1 < size && arr[left] < arr[left + 1] ? left +1: left;
largest = arr[largest] > arr[index]? largest: index;
if(largest == index) {
break;
}
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = new int[]{3, 6, 3, 2, 9, 0};
System.out.println(Arrays.toString(arr));
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
}
1.9 Code09_MediumNumber
在一段数据流中，找到中位数
public class Code09_MediumNumber {
private int cnt = 0;
private PriorityQueue<Integer> low = new PriorityQueue<Integer>();
private PriorityQueue<Integer> high = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
public void Insert(Integer num) {
cnt++;
if((cnt & 1) == 1) {
if(!low.isEmpty() && num > low.peek()) {
low.offer(num);
num = low.poll();
}
high.offer(num);
}else {
if(!high.isEmpty() && num < high.peek()) {
high.offer(num);
num = high.poll();
}
low.offer(num);
}
}
public Double GerMidian() {
double res = 0;
if((cnt & 1) == 1) {
res = high.peek();
}else {
res = (high.peek() + low.peek()) / 2.0;
}
return res;
}
}
1.10 Code10_MaxGap
给定一个数组，求如果排序之后，相邻两个数的最大差值，时间复杂度O(N)，不能基于比较的排序。
public class Code10_MaxGap {
public static int maxGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int len = nums.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < len; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
if (min == max) {
return 0;
}
boolean[] hasNum = new boolean[len + 1];
int[] maxs = new int[len + 1];
int[] mins = new int[len + 1];
int bid;
for (int i = 0; i < len; i++) {
bid = bucket(nums[i], len, min, max);
mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
hasNum[bid] = true;
}
int res = 0;
int lastMax = maxs[0];
for (int i = 1; i <= len; i++) {
if (hasNum[i]) {
res = Math.max(res, mins[i] - lastMax);
lastMax = maxs[i];
}
}
return res;
}
private static int bucket(long num, long len, long min, long max) {
return (int) ((num - min) * len / (max - min));
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = new int[]{1,5,2,1,5,2,7,6,9,2};
// Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
System.out.print(maxGap(arr));
}
}
1.11 code11_Array_Stack_Queue
用数组结构实现大小固定的队列和栈。
注意队列和栈需要的类属性和指针的变化。
public class code11_Array_Stack_Queue {
public static class ArrayStack {
private Integer[] arr;
private Integer size;// ջ��ָ��
public ArrayStack(int initsize) {
if (initsize < 0) {
throw new IllegalArgumentException("size is less than 0");
}
arr = new Integer[initsize];
size = 0;
}
public Integer peek() {
if (size == 0) {
return null;
}
return arr[size - 1];
}
public void push(int obj) {
if (size == arr.length) {
throw new ArrayIndexOutOfBoundsException("the stack is full");
}
arr[size++] = obj;
}
public Integer pop() {
if (size == 0) {
throw new ArrayIndexOutOfBoundsException("the stack is empty");
}
return arr[--size];
}
}
public static class ArrayQueue {
private Integer[] arr;
private Integer size;
private Integer first;
private Integer last;
public ArrayQueue(int initSize) {
if (initSize < 0) {
throw new IllegalArgumentException("size is less than 0");
}
arr = new Integer[initSize];
size = 0;
first = 0;
last = 0;
}
public Integer peek() {
if (size == 0) {
return null;
}
return arr[first];
}
public void push(int obj) {
if (size == arr.length) {
throw new ArrayIndexOutOfBoundsException("the queue is full");
}
size++;
arr[last] = obj;
last = last == arr.length - 1 ? 0 : last + 1;
}
public Integer poll() {
if (size == 0) {
throw new ArrayIndexOutOfBoundsException("the queue is empty");
}
size--;
int temp = arr[first];
first = first == arr.length - 1 ? 0 : first + 1;
return temp;
}
}
}
1.12 Code12_GetMinStack
实现一个特殊的栈，在栈的基础上增加返回最小元素的操作。
· 思路：准备两个栈，data栈正常压栈，Min栈需要比较当前数和栈顶数的大小。
public class Code12_GetMinStack {
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public Code12_GetMinStack() {
this.stackData = new Stack<Integer>();
this.stackMin = new Stack<Integer>();
}
public void push(int newNum) {
if (this.stackMin.isEmpty()) {
this.stackMin.push(newNum);
} else if (newNum < this.getMin()) {
this.stackMin.push(newNum);
} else {
int newMin = this.stackMin.peek();
this.stackMin.push(newMin);
}
this.stackData.push(newNum);
}
public Integer getMin() {
if (this.stackMin.isEmpty()) {
throw new RuntimeException("your stack is empty");
}
return this.stackMin.peek();
}
}
1.13 Code13_stack_convert_Queue
public class Code13_stack_convert_Queue {
public static class StackToQueue{
private Stack<Integer> stackPush;
private Stack<Integer> stackPop;
public StackToQueue() {
this.stackPush = new Stack<Integer>();
this.stackPop = new Stack<Integer>();
}
public void push(int pushInt) {
stackPush.push(pushInt);
}
public int poll() {
//empty()��IsEmpty������ͬ��
if(stackPop.isEmpty() && stackPush.isEmpty()) {
throw new RuntimeException("queue is empty");
}else if(stackPop.isEmpty()) {
while(!stackPush.isEmpty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}
public int peek() {
if(stackPop.isEmpty() && stackPush.isEmpty()) {
throw new RuntimeException("queue is empty");
}else if(stackPop.isEmpty()) {
while(!stackPush.isEmpty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.peek();
}
}
public static class QueueToStack{
private Queue<Integer> queue;
private Queue<Integer> help;
public QueueToStack() {
this.queue = new LinkedList<Integer>();
this.help = new LinkedList<Integer>();
}
public void push(int pushInt) {
queue.offer(pushInt);
}
public int peek() {
if(queue.isEmpty()) {
throw new RuntimeException("Stack is empty");
}
while(queue.size() != 1) {
help.offer(queue.poll());
}
int res = queue.poll();
Queue<Integer> temp = help;
help = queue;
queue = temp;
return res;
}
}
}
1.14 Code14_PrintMatrixSpiralOrder
public class Code14_PrintMatrixSpiralOrder {
public static void printMatrix(int[][] matrix) {
int tr = 0;
int tc = 0;
int dr = matrix.length - 1;// ����
int dc = matrix[0].length - 1;// ����
while (tr <= dr && tc <= dc) {
printEdge(matrix, tr++, tc++, dr--, dc--);
}
}
public static void printEdge(int[][] m, int tr, int tc, int dr, int dc) {
if (tr == dr) {
for (int i = tc; i <= dc; i++) {
System.out.print(m[tr][i] + " ");
}
} else if (tc == dc) {
for (int i = tr; i <= dr; i++) {
System.out.print(m[i][tc] + " ");
}
} else {
int curC = tc;
int curR = tr;
while (curC != dc) {
System.out.print(m[tr][curC] + " ");
curC++;
}
while (curR != dr) {
System.out.print(m[curR][dc] + " ");
curR++;
}
while (curC != tc) {
System.out.print(m[dr][curC] + " ");
curC--;
}
while (curR != tr) {
System.out.print(m[curR][tc] + " ");
curR--;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
printMatrix(matrix);
}
}
1.15 Code15_RotateMatrix
public class Code15_RotateMatrix {
public static void rotate(int[][] matrix) {
int ax = 0;
int ay = 0;
int bx = matrix.length - 1;
int by = matrix[0].length - 1;
while(ax < bx) {
rotateEdge(matrix, ax++, ay++, bx--, by--);
}
}
public static void rotateEdge(int[][] m, int ax, int ay, int bx, int by) {
int times = by - ay;
int tmp = 0;
for(int i = 0; i != times; i++) {
tmp = m[ax][ay + i];
m[ax][ay + i] = m[bx - i][ay];
m[bx - i][ay] = m[bx][by - i];
m[bx][by - i] = m[ax + i][by];
m[ax + i][by] = tmp;
}
}
public static void printMatrix(int[][] matrix) {
for(int i = 0; i < matrix.length; i++) {
for(int j = 0; j < matrix[0].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
printMatrix(matrix);
rotate(matrix);
System.out.println("==============");
printMatrix(matrix);
}
}
1.16 Code16_ZigZagPrintMatrix
public class Code16_ZigZagPrintMatrix {
public static void printMatrixZigZag(int[][] matrix) {
int tR = 0;
int tC = 0;
int dR = 0;
int dC = 0;
int endR = matrix.length - 1;
int endC = matrix[0].length - 1;
boolean fromUp = false;
while (tR != endR + 1) {
printLevel(matrix, tR, tC, dR, dC, fromUp);
tR = tC == endC ? tR + 1 : tR;
tC = tC == endC ? tC : tC + 1;
dC = dR == endR ? dC + 1 : dC;
dR = dR == endR ? dR : dR + 1;
fromUp = !fromUp;
}
System.out.println();
}
public static void printLevel(int[][] m, int tR, int tC, int dR, int dC,
boolean f) {
if (f) {
while (tR != dR + 1) {
System.out.print(m[tR++][tC--] + " ");
}
} else {
while (dR != tR - 1) {
System.out.print(m[dR--][dC++] + " ");
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
printMatrixZigZag(matrix);
}
}
1.17 Code17_FindNumInSortedMatrix
public class Code17_FindNumInSortedMatrix {
public static boolean isContains(int[][] matrix, int K) {
int row = 0;
int col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
if (matrix[row][col] == K) {
return true;
} else if (matrix[row][col] < K) {
row++;
} else {
col--;
}
}
return false;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] matrix = new int[][] { { 0, 1, 2, 3, 4, 5, 6 }, // 0
{ 10, 12, 13, 15, 16, 17, 18 }, // 1
{ 23, 24, 25, 26, 27, 28, 29 }, // 2
{ 44, 45, 46, 47, 48, 49, 50 }, // 3
{ 65, 66, 67, 68, 69, 70, 71 }, // 4
{ 96, 97, 98, 99, 100, 111, 122 }, // 5
{ 166, 176, 186, 187, 190, 195, 200 }, // 6
{ 233, 243, 321, 341, 356, 370, 380 } // 7
};
int K = 233;
System.out.println(isContains(matrix, K));
}
}
1.18 Code18_IsPalindromeList
public class Code18_IsPalindromeList {
public static class Node{
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
//�۵�����
public static boolean isPalindrome(Node head) {
if( head == null || head.next == null) {
return true;
}
Node n1 = head;
Node n2 = head;
while(n2.next != null && n2.next.next != null) {
n1 = n1.next;
n2 = n2.next.next;
}
//n1Ϊ�е�
n2 = n1.next;
n1.next = null;
Node n3 = null;
while(n2 != null) {
n3 = n2.next;
n2.next = n1;
n1 = n2;
n2 = n3;
}
n3 = n1;
n2 = head;
boolean res = true;
while(n1 != null && n2 != null) {
if(n1.value != n2.value) {
res = false;
break;
}
n1 = n1.next;
n2 = n2.next;
}
//��ԭ����
n1 = n3.next;
n3.next = null;
while(n1 != null) {
n2 = n1.next;
n1.next = n3;
n3 = n1;
n1 = n2;
}
return res;
}
}
1.19 Code19_SmallerEqualBigger
public class Code19_SmallerEqualBigger {
public static class Node{
public int value;
public Node next;
public Node (int data) {
this.value = data;
}
}
public static Node listPartition(Node head, int pivot) {
if(head == null) {
return head;
}
Node cur = head;
int i = 0;
while(cur != null) {
i++;
cur = cur.next;
}
Node[] nodeArr = new Node[i];
i = 0;
cur = head;
//������ת�ɽڵ�����
for(; i != nodeArr.length; i++) {
nodeArr[i] = cur;
cur = cur.next;
}
arrPartition(nodeArr, pivot);
for(i = 1; i < nodeArr.length; i++) {
nodeArr[i - 1].next = nodeArr[i];
}
nodeArr[i - 1].next = null;
return nodeArr[0];
}
public static void arrPartition (Node[] nodeArr, int pivot) {
int less = -1;
int more = nodeArr.length;
int index = 0;
while(less < more) {
if(nodeArr[index].value < pivot) {
swap(nodeArr, index++, ++less);
}else if(nodeArr[index].value > pivot) {
swap(nodeArr, index, --more);
}else {
index++;
}
}
}
public static void swap(Node[] arr, int a, int b) {
Node temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
1.20 Code20_CopyListWithRandom
public class Code20_CopyListWithRandom {
public static class Node{
public int value;
public Node next;
public Node rand;
public Node(int data) {
this.value = data;
}
}
//���븴�ƽڵ�
public static Node copyListWithRand(Node head) {
if(head == null) {
return null;
}
Node cur = head;
Node next = null;
while(cur != null) {
next = cur.next;
cur.next = new Node(cur.value);
cur.next.next = next;
cur = next;
}
cur = head;
Node curCopy = null;
while(cur != null) {
next = cur.next.next;
curCopy = cur.next;
curCopy.rand = cur.rand == null ? null : cur.rand.next;
cur = next;
}
Node res = head.next;
cur = head;
while(cur != null) {
next = cur.next.next;
curCopy = cur.next;
cur.next = next;
curCopy.next = next != null ? next.next : null;
cur = next;
}
return res;
}
}
1.21 Code21_FindFirstIntersectNode
public class Code21_FindFirstIntersectNode {
public static class Node{
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public static Node getIntersectNode(Node head1, Node head2) {
if(head1 == null || head2 == null) {
return null;
}
Node loop1 = getLoopNode(head1);
Node loop2 = getLoopNode(head2);
if(loop1 == null && loop2 == null) {
return noLoop(head1, head2);
}
if(loop1 != null && loop2 != null) {
return bothLoop(head1, loop1, head2, loop2);
}
return null;
}
private static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
// TODO �Զ����ɵķ������
Node cur1 = null;
Node cur2 = null;
if(loop1 == loop2) {
cur1 = head1;
cur2 = head2;
int n = 0;
while(cur1 != loop1) {
n++;
cur1 = cur1.next;
}
while(cur2 != loop2) {
n--;
cur2 = cur2.next;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while(n != 0) {
n--;
cur1 = cur1.next;
}
while(cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}else {
cur1 = loop1.next;
while(cur1 != loop1) {
if(cur1 == loop2) {
return loop1;
}
cur1 = cur1.next;
}
return null;
}
}
private static Node noLoop(Node head1, Node head2) {
// TODO �Զ����ɵķ������
Node cur1 = head1;
Node cur2 = head2;
int n = 0;
while(cur1.next != null) {
n++;
cur1 = cur1.next;
}
while(cur2.next != null) {
n--;
cur2 = cur2.next;
}
if(cur1 != cur2) {
return null;
}
cur1 = n > 0 ? head1: head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while(n != 0) {
n--;
cur1 = cur1.next;
}
while(cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
public static Node getLoopNode(Node head) {
// TODO �Զ����ɵķ������
if(head == null || head.next == null || head.next.next == null) {
return null;
}
Node n1 = head.next;
Node n2 = head.next.next;
while(n1 != n2) {
if(n2.next == null || n2.next.next == null) {
return null;
}
n1 = n1.next;
n2 = n2.next.next;
}
n2 = head;
while(n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}
return n1;
}
}
