MergeTwoSortedLists
*
* @param left
* @param right
* @return
*/
public Node mergeList(Node left, Node right) {
Node head = new Node();
Node result = head;
/**
* 思想就是两个链表同时遍历，将更的元素插入结果中，同时更更大的元素所属的链表的指针向下移动
*/
while (!(null == left && null == right)) {
Node tmp;
if (left == null) {
result.next = right;
break;
} else if (right == null) {
result.next = left;
break;
} else if (left.e >= right.e) {
tmp = left;
result.next = left;
result = tmp;
left = left.next;
} else {
tmp = right;
result.next = right;
result = tmp;
right = right.next;
}
}
return head.next;
}
public static void main(String[] args) {
Node head = new Node();
head.next = new Node(7,
new Node(2,
new Node(5,
new Node(4,
new Node(3,
new Node(6,
new Node(11, null)
)
)
)
)
)
);
int length = 0;
for (Node e = head.next; null != e; e = e.next) {
length++;
}
LinkedListMergeSort sort = new LinkedListMergeSort();
head.next = sort.mergeSort(head.next, length);
for (Node n = head.next; n != null; n = n.next) {
System.out.println(n.e);
}
}
}
```
# 数组右移 k 次
```java
/**
* 数组右移K次, 原数组 [1, 2, 3, 4, 5, 6, 7] 右移3次后结果为 [5,6,7,1,2,3,4]
*
* 基本思路：不开辟新的数组空间的情况下考虑在原属组上进行操作
* 1 将数组倒置，这样后k个元素就跑到了数组的前面，然后反转一下即可
* 2 同理后 len-k个元素只需要翻转就完成数组的k次移动
*
* @author 656369960@qq.com
* @date 12/7/2018 1:38 PM
* @since 1.0
*/
public class ArrayKShift {
public void arrayKShift(int[] array, int k) {
/**
* constrictions
*/
if (array == null || 0 == array.length) {
return ;
}
k = k % array.length;
if (0 > k) {
return;
}
/**
* reverse array , e.g: [1, 2, 3 ,4] to [4,3,2,1]
*/
for (int i = 0; i < array.length / 2; i++) {
int tmp = array[i];
array[i] = array[array.length - 1 - i];
array[array.length - 1 - i] = tmp;
}
/**
* first k element reverse
*/
for (int i = 0; i < k / 2; i++) {
int tmp = array[i];
array[i] = array[k - 1 - i];
array[k - 1 - i] = tmp;
}
/**
* last length - k element reverse
*/
for (int i = k; i < k + (array.length - k ) / 2; i ++) {
int tmp = array[i];
array[i] = array[array.length - 1 - i + k];
array[array.length - 1 - i + k] = tmp;
}
}
public static void main(String[] args) {
int[] array = {1, 2, 3 ,4, 5, 6, 7};
ArrayKShift shift = new ArrayKShift();
shift.arrayKShift(array, 6);
Arrays.stream(array).forEach(o -> {
System.out.println(o);
});
}
}
```
# 交替打印奇偶数
## lock 版
```java
/**
* Function: 两个线程交替执行打印 1~100
*
* lock 版
*
* @author crossoverJie
* Date: 11/02/2018 10:04
* @since JDK 1.8
*/
public class TwoThread {
private int start = 1;
/**
* 对 flag 的写入虽然加锁保证了线程安全，但读取的时候由于 不是 volatile 所以可能会读取到旧值
*
*/
private volatile boolean flag = false;
/**
* 重入锁
*/
private final static Lock LOCK = new ReentrantLock();
public static void main(String[] args) {
TwoThread twoThread = new TwoThread();
Thread t1 = new Thread(new OuNum(twoThread));
t1.setName("t1");
Thread t2 = new Thread(new JiNum(twoThread));
t2.setName("t2");
t1.start();
t2.start();
}
/**
* 偶数线程
*/
public static class OuNum implements Runnable {
private TwoThread number;
public OuNum(TwoThread number) {
this.number = number;
}
@Override
public void run() {
while (number.start <= 1000) {
if (number.flag) {
try {
LOCK.lock();
System.out.println(Thread.currentThread().getName() + "+-+" + number.start);
number.start++;
number.flag = false;
} finally {
LOCK.unlock();
}
}
}
}
}
/**
* 奇数线程
*/
public static class JiNum implements Runnable {
private TwoThread number;
public JiNum(TwoThread number) {
this.number = number;
}
@Override
public void run() {
while (number.start <= 1000) {
if (!number.flag) {
try {
LOCK.lock();
System.out.println(Thread.currentThread().getName() + "+-+" + number.start);
number.start++;
number.flag = true;
} finally {
LOCK.unlock();
}
}
}
}
}
}
```
## 等待通知版
```java
/**
* Function:两个线程交替执行打印 1~100
* 等待通知机制版
*
* @author crossoverJie
* Date: 07/03/2018 13:19
* @since JDK 1.8
*/
public class TwoThreadWaitNotify {
private int start = 1;
private boolean flag = false;
public static void main(String[] args) {
TwoThreadWaitNotify twoThread = new TwoThreadWaitNotify();
Thread t1 = new Thread(new OuNum(twoThread));
t1.setName("t1");
Thread t2 = new Thread(new JiNum(twoThread));
t2.setName("t2");
t1.start();
t2.start();
}
/**
* 偶数线程
*/
public static class OuNum implements Runnable {
private TwoThreadWaitNotify number;
public OuNum(TwoThreadWaitNotify number) {
this.number = number;
}
@Override
public void run() {
while (number.start <= 100) {
synchronized (TwoThreadWaitNotify.class) {
System.out.println("偶数线程抢到锁了");
if (number.flag) {
System.out.println(Thread.currentThread().getName() + "+-+偶数" + number.start);
number.start++;
number.flag = false;
TwoThreadWaitNotify.class.notify();
}else {
try {
TwoThreadWaitNotify.class.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}
}
/**
* 奇数线程
*/
public static class JiNum implements Runnable {
private TwoThreadWaitNotify number;
public JiNum(TwoThreadWaitNotify number) {
this.number = number;
}
@Override
public void run() {
while (number.start <= 100) {
synchronized (TwoThreadWaitNotify.class) {
System.out.println("奇数线程抢到锁了");
if (!number.flag) {
System.out.println(Thread.currentThread().getName() + "+-+奇数" + number.start);
number.start++;
number.flag = true;
TwoThreadWaitNotify.class.notify();
}else {
try {
TwoThreadWaitNotify.class.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}
}
}
```
## 非阻塞版
```java
/**
* Function: 两个线程交替执行打印 1~100
* * non blocking 版： * 两个线程轮询volatile变量(flag) * 线程一"看到"flag值为1时执行代码并将flag设置为0, * 线程二"看到"flag值为0时执行代码并将flag设置未1, * 2个线程不断轮询直到满足条件退出 * * @author twoyao * Date: 05/07/2018 * @since JDK 1.8 */ public class TwoThreadNonBlocking implements Runnable { /** * 当flag为1时只有奇数线程可以执行，并将其置为0 * 当flag为0时只有偶数线程可以执行，并将其置为1 */ private volatile static int flag = 1; private int start; private int end; private String name; private TwoThreadNonBlocking(int start, int end, String name) { this.name = name; this.start = start; this.end = end; } @Override public void run() { while (start <= end) { int f = flag; if ((start & 0x01) == f) { System.out.println(name + "+-+" + start); start += 2; // 因为只可能同时存在一个线程修改该值，所以不会存在竞争 flag ^= 0x1; } } } public static void main(String[] args) { new Thread(new TwoThreadNonBlocking(1, 100, "t1")).start(); new Thread(new TwoThreadNonBlocking(2, 100, "t2")).start(); } } ```