合并两个有序的链表

描述

给定两个有序的链表，合并成一个有序的链表。

图示

思路分析

1） 将head头指针指向两个链表当中第一个较小的结点，用来标记合并后的链表头。
2）定义一个结点s，用来链链表。
3）定义一个结点p，用来遍历第一个链表，指向第一个链表的第一个结点。
4）定义一个结点q，用来遍历第二个链表，指向第二个链表的第二个结点。
5）因为s是用来链链表的，所以首先s指向小的结点，即指向head。
6）比较p和q指向的结点的value值，谁小往后走一个结点。
7）然后s去链接p和q指向的value值较小的结点，如果链接的是q指向的结点，q往后走一个结点，如果链接的是p，p往后走一个结点，链接完成后，s往后走一个结点，等待链接下一个结点。
8）重复步骤7，直到p和q当中的一个为null。
9）因为其中一个链表已经链接完成，为了链接另一个链表的剩余部分，更新s指针（如果p为null,s指向q,如果q为null，s指向p）
首先使head指向两个链表中第一个结点较小的结点，s同时也指向两个链表中第一个结点较小的结点，此时p执行s的下一个结点，q指向第二个链表中的第一个结点。

现在开始链链表

得到结果

代码

/**
 * Definition for singly-linked list.
 * class Node {
 *     int value;
 *     Node next;
 *     Node(int x) {
 *        value = x;
 *        next = null;
 *     }
 * }
 */
public class SingleLink {
    private Node head;//用来标记链表的起始位置
    
    //合并两个有序链表
    public void mergeeTwoLink(SingleLink link) {
        if (link == null) {
            return;
        }

        Node s;//用于链链表
        Node p = head;//用于遍历第一个链表
        Node q = link.head;//用于遍历第二个链表

        //标记合并后的链表头
        head = (p.value < q.value) < 0) ? p : q;

        //初始化s
        s = head;

        //谁小谁往后走
        if (head == p) {
            p = p.next;
        } else {
            q = q.next;
        }

        while (p != null && q != null) {
            if (p.value < q.value) {
                s.next = p;
                p = p.next;
            } else {
                s.next = q;
                q = q.next;
            }
            s = s.next;
        }
       
       //其中一个链表已经链完，为了链接另一个链表的剩余部分
       //如果p为null,s指向q,如果q为null，s指向p
       s.next = p == null ? q : p;
}