剑指offer面试题17 合并俩个排序的列表
public class Seventeen {
public static void main(String[] args) {
LinkList lista = new LinkList();
lista.addNode(1);
lista.addNode(3);
lista.addNode(5);
lista.addNode(7);
LinkList listb = new LinkList();
listb.addNode(2);
listb.addNode(4);
listb.addNode(6);
listb.addNode(8);
LinkNode head = merge(lista.head,listb.head);
print(head);
}
public static LinkNode merge(LinkNode nodea,LinkNode nodeb) {
if (nodea == null) {
return nodeb;
}
if (nodeb == null) {
return nodea;
}
LinkNode pHead = null;
if (nodea.val < nodeb.val) {
pHead = nodea;
pHead.next = merge(nodea.next,nodeb);
} else {
pHead = nodeb;
pHead.next = merge(nodea,nodeb.next);
}
return pHead;
}
//正序打印
public static void print(LinkNode node) {
while(node != null) {
System.out.print(node.val);
System.out.print(" ");
node = node.next;
}
System.out.println();
}
}
public class LinkNode {
int val;
LinkNode next;
public LinkNode(int data) {
this.val = data;
this.next = null;
}
}
public class LinkList {
LinkNode head;
public LinkList() {
this.head = null;
}
//添加元素
public void addNode(int data) {
LinkNode node = new LinkNode(data);
if (this.head == null) {
this.head = node;
} else {
LinkNode cur = this.head;
while(cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}
}