/**
 * 两条有序列表合并之后仍然有序
 * 同时不断遍历两个链表，取出小的追加到新的头节点后，直至两者其中一个为空
 * 再将另一者追加的新链表最后
 * 
 * @return 两个有序的链表合并后得到的链表
 */
public static Node mergeOrderedLinkedList(Node p1, Node p2) {
	// 创建一个头节点
	Node head = new Node();
	// 尾指针指向头节点
	Node tail = head;
	// 遍历两个链表，短的链表接受后循环停止
	while (p1 != null && p2 != null) {
		// 比较两个链表中的节点
		// 如果链表1的当前节点小
		if (p1.data < p2.data) {
			// 小的链表1的当前节点连接到尾节点上。
			tail.next = p1;
			// 链表1的当前节点已经连接到结果链表上了，
			// 链表1的当前节点向前走一步
			p1 = p1.next;
		} else {
			// 如果是链表2的当前节点比较小
			// 把链表2的当前节点接到合并链表的尾节点上
			tail.next = p2;
			// 链表2的当前节点向前走一步
			p2 = p2.next;
		}
		// 合并链表尾指针向前走一步
		tail = tail.next;
	}
	// 长的链表剩下的部分接到尾节点上
	tail.next = (p1 == null) ? p2 : p1;
	return head.next;
}

int[] a = { 1, 4, 5, 8, 9 };
int[] b = { 2, 3, 6, 7, 10, 11, 12 };
Node nodeA = Node.createLinkByTail(a);
Node nodeB = Node.createLinkByTail(b);
Node.printNode(nodeA);
Node.printNode(nodeB);
Node mernNode = Node.mergeOrderedLinkedList(nodeA, nodeB);
Node.printNode(mernNode);

head-->1-->4-->5-->8-->9
head-->2-->3-->6-->7-->10-->11-->12
head-->1-->2-->3-->4-->5-->6-->7-->8-->9-->10-->11-->12

int[] b = { 1, 4, 5, 8, 9 };
int[] a = { 2, 3, 6, 7, 10, 11, 12 };

/**
 * 删除所有查找到的节点
 * 
 * @param head 链表的头指针
 * @param data 要删除的节点的数值
 * @return 删除链表中的所有符合的节点后的链表的头指针。
 */
public static Node delectAllNodeInLink(Node head, int data) {
    // 要删除的是头节点的情况
    while (head.data == data) {
        // 头指针后移，越过该节点
        head = head.next;
    }
    // 如果要删除的是中间的节点
    // 没有重复的前一个节点的指针
    Node p = head;
    // 当前节点的指针
    Node c = p;
    // 当前节点的后面还有节点时
    while (c.next != null) {
        // 当前节点向前走一步
        c = c.next;
        if (c.data == data) {
            // 断开前面的链表与当前链表的连接
            p.next = null;
            // 当前节点后面的链表接到当前节点前面的链表的尾巴上
            p.next = c.next;
        } else {
            // 保存下当前遍历的节点，以便下次遍历的时候知道它上一个节点是谁
            p = c;
        }
    }
    return head;
}

/**
 * 从链表中删除一个节点
 * 
 * @param head 链表的头指针
 * @param data 要删除的节点中的数据
 * @return 删除指定节点后的链表的头指针。
 */
public static Node deleteNodeInLink(Node head, int data) {
    // 如果要删除的是头节点
    if (head.data == data) {
        // 头指针向后移动一格，越过头节点，也就从链表中删除该节点
        head = head.next;
        return head;
    }
    // 如果不是头节点
    // 当前遍历的节点的前一个节点
    Node previous = head;
    // 当前遍历的节点
    Node current = previous;
    // 如果当前节点后面有节点的话
    while (current.next != null) {
        // 移动到后一个节点
        current = current.next;
        // 如果找到要删除的节点
        if (current.data == data) {
            // 前面的链表 断开与要删除的节点的之间的连接
            previous.next = null;
            // 把要删除的节点后面的节点接到它前面的节点上
            previous.next = current.next;
            // 断开要删除的节点和它后面的节点之间的连接
            current.next = null;
            // 已经删除好了，退出
            return head;
        } else {
            previous = current;
        }
    }
    return head;
}

/**
 * 颠倒链表，使得链表的尾部变成头部
 * 
 * @param head 链表头节点的引用
 * @return 颠倒后的链表的头节点的地址
 */
public static Node invertLink(Node head) {
	// 颠倒后的新链表的头节点
	Node newHead = null;
	// 颠倒后的新链表的尾节点
	Node newTail = null;
	// 倒数第二个节点
	Node secondToLast = null;
	// 最后一个节点
	Node last = null;
	// 如果头节点后面还有节点的话
	while (head.next != null) {
		// 查找倒数第2的节点
		secondToLast = findSecondToLastNode(head);
		// System.out.print("倒数第2=" + secondToLast.data);
		// 倒数第1个节点
		last = secondToLast.next;
		// System.out.println(",倒数第1=" + last.data);
		// 断开最后一个节点
		secondToLast.next = null;

		if (newHead == null) {
			// 第一次断开的尾节点,作为新链表的头节点。
			newHead = last;
			newTail = last;
		} else {
			// 旧链表的尾节点作为新链表的尾节点
			newTail.next = last;
			// 新加入的节点作为尾节点
			newTail = newTail.next;
		}
	}
	last=null;
	secondToLast=null;
	// 处理旧链表的最后一个节点，也就是头节点
	// 头节点作为最后的尾节点
	newTail.next = head;
	// 新加入的节点作为尾节点
	newTail = newTail.next;
	// 原来的头指针断开与头节点的连接
	head = null;
	// 返回新链表的头节点
	return newHead;
}

/**
 * 查找倒数第2的节点
 * 
 * @param head 链表的头节点的引用
 * @return 链表倒数第二节点的引用
 */
private static Node findSecondToLastNode(Node head) {
    Node p = head;
    while (p.next.next != null) {
        p = p.next;
    }
    return p;
}