先自己实现一个单向的链表
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;}@Overridepublic String toString() {return item.toString();}}}题目中链表是有序的，所以不需要考虑排序问题
mergeeSingleLinkedList 方法合并链表，思路
- 获取两个链表中的首节点
- 比较首节点大小，结果分别存入 small、large 节点
- 把 small 节点存入新的链表，再比较获取 small.next和 large，结果分别存入 small、large 节点
- 直到 small.next 和 large 都为 null
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
