先自己实现一个单向的链表
package constxiong.interview;
/**
* 单向链表
* @author ConstXiong
* @param <E>
*/
class SingleLinkedList<E> {
int size = 0;
Node<E> first;
Node<E> last;
public SingleLinkedList() {
}
public void add(E e) {
Node<E> l = last;
Node<E> item = new Node<E>(e, null);
last = item;
if (l == null) {
this.first = item;
} else {
l.next = item;
}
size++;
}
/**
* 打印链表
* @param ll
*/
public void print() {
for (Node<E> item = first; item != null; item = item.next) {
System.out.print(item + " ");
}
}
/**
* 单向链表中的节点
* @author ConstXiong
* @param <E>
*/
public static class Node<E> {
E item;
Node<E> next;
Node(E item, Node<E> next) {
this.item = item;
this.next = next;
}
public E get() {
return item;
}
@Override
public String toString() {
return item.toString();
}
}
}
题目中链表是有序的,所以不需要考虑排序问题
mergeeSingleLinkedList 方法合并链表,思路
package constxiong.interview;
import constxiong.interview.SingleLinkedList.Node;
/**
* 链表两个有序列表
* @author ConstXiong
* @date 2019-11-06 09:37:14
*/
public class TestMergeLinkedList {
public static void main(String[] args) {
SingleLinkedList<Integer> ll1 = new SingleLinkedList<Integer>();
ll1.add(3);
ll1.add(8);
ll1.add(19);
SingleLinkedList<Integer> ll2 = new SingleLinkedList<Integer>();
ll2.add(3);
ll2.add(10);
ll2.add(17);
mergeeSingleLinkedList(ll1, ll2).print();
}
/**
* 合并两个有序列表
* @param ll1
* @param ll2
* @return
*/
private static SingleLinkedList<Integer> mergeeSingleLinkedList(SingleLinkedList<Integer> ll1, SingleLinkedList<Integer> ll2) {
if (isEmpty(ll1) || isEmpty(ll2)) {
return isEmpty(ll1) ? ll2 : ll1;
}
SingleLinkedList<Integer> ll = new SingleLinkedList<Integer>();
Node<Integer> ll1Node = ll1.first;
Node<Integer> ll2Node = ll2.first;
Node<Integer> small = ll1Node.get() <= ll2Node.get() ? ll1Node : ll2Node;
Node<Integer> large = ll1Node.get() > ll2Node.get() ? ll1Node : ll2Node;
do {
ll.add(small.get());
Node<Integer> smallNext = small.next;
if (smallNext == null || large == null) {
small = smallNext == null ? large : smallNext;
large = null;
} else {
small = smallNext.get() <= large.get() ? smallNext : large;
large = smallNext.get() > large.get() ? smallNext : large;
}
}
while (small != null);
return ll;
}
/**
* 测试链表存储是否OK
*/
public static void testSingleLinkedListIsOk() {
SingleLinkedList<Integer> ll = new SingleLinkedList<Integer>();
ll.add(3);
ll.add(8);
ll.add(19);
ll.print();
}
private static boolean isEmpty(SingleLinkedList<Integer> ll) {
if (ll == null || ll.size == 0) {
return true;
}
return false;
}
}
打印结果
3 3 8 10 17 19