剑指offer面试题17-归拢两个排序的链表

剑指offer面试题17-合并两个排序的链表

题目：

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是按照递增排序的。

链表结构如下：

package com.aii.algorithm;

public class Node {
	int value;
	Node next;

	public Node(int value) {
		this.value = value;
	}

	@Override
	public String toString() {
		return "Node [value=" + value + ", next=" + next + "]";
	}

}

这个和归并排序差不多，只要记录好指针，不要让链表断掉就行了。

以及一些特殊情况的判断。

package com.aii.algorithm;

/**
 * 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是按照递增排序的。
 * */
public class MergeLinkedList {
	// 循环的方法
	public Node merge(Node n1, Node n2) {
		// 用于记录头节点
		Node head = null;
		Node newCurrent = null;
		Node n1Current = n1;
		Node n2Current = n2;
		// 先处理第一个头结点。
		if (n1Current != null && n2Current != null) {
			if (n1Current.value > n2Current.value) {
				newCurrent = n2Current;
				n2Current = n2Current.next;
			} else {
				newCurrent = n1Current;
				n1Current = n1Current.next;
			}
		} else if (n1Current != null && n2Current == null) {
			newCurrent = n1Current;
			n1Current = n1Current.next;
		} else if (n1Current == null && n2Current != null) {
			newCurrent = n2Current;
			n2Current = n2Current.next;
		}
		// 记录，用于返回，防止被覆盖
		head = newCurrent;

		// 当2个链表都不为空的情况下，遍历取小的往合并都的链表放
		while (n1Current != null && n2Current != null) {
			if (n1Current.value > n2Current.value) {
				newCurrent.next = n2Current;
				newCurrent = n2Current;
				n2Current = n2Current.next;
			} else {
				newCurrent.next = n1Current;
				newCurrent = n1Current;
				n1Current = n1Current.next;
			}
		}
		// one is empty
		if (n1Current == null && n2Current != null) {
			newCurrent.next = n2Current;
		}
		if (n2Current == null && n1Current != null) {
			newCurrent.next = n1Current;
		}
		return head;
	}

	// 递归的方法
	public Node merge2(Node n1, Node n2) {
		if (n1 == null && n2 == null) {
			return null;
		}
		if (n1 == null && n2 != null) {
			return n2;
		}
		if (n1 != null && n2 == null) {
			return n1;
		}
		// n1!=null && n2!=null
		if (n1.value > n2.value) {
			n2.next = merge2(n1, n2.next);
			return n2;
		}
		n1.next = merge2(n1.next, n2);
		return n1;
	}
}