JZ16 — 合并两个排序的链表

0 题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

1 解法一

使用两个指针，分别指向两个链表，每次添加较小的那个到新的链表中即可。注意，当其中一个链表的结点全部都被添加后，将另外一个链表剩余部分全部添加到新链表。
创建一个无用的头结点，便于操作。

1.1 开辟新的空间，不影响原链表

1.1.1 C++

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution
{
public:
    ListNode *Merge(ListNode *pHead1, ListNode *pHead2)
    {
        ListNode *head = new ListNode(0), *current = head;
        while (pHead1 && pHead2)
        {
            if (pHead1->val <= pHead2->val)
            {
                current->next = new ListNode(pHead1->val);
                pHead1 = pHead1->next;
            }
            else
            {
                current->next = new ListNode(pHead2->val);
                pHead2 = pHead2->next;
            }
            current = current->next;
        }
        while (pHead1)
        {
            current->next = new ListNode(pHead1->val);
            pHead1 = pHead1->next;
            current = current->next;
        }
        while (pHead2)
        {
            current->next = new ListNode(pHead2->val);
            pHead2 = pHead2->next;
            current = current->next;
        }
        return head->next;
    }
};

1.1.2 Java

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(0), current = head;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = new ListNode(list1.val);
                list1 = list1.next;
            } else {
                current.next = new ListNode(list2.val);
                list2 = list2.next;
            }
            current = current.next;
        }
        while (list1 != null) {
            current.next = new ListNode(list1.val);
            list1 = list1.next;
            current = current.next;
        }
        while (list2 != null) {
            current.next = new ListNode(list2.val);
            list2 = list2.next;
            current = current.next;
        }
        return head.next;
    }
}

1.2 不开辟新空间，直接在原链表进行修改

1.2.1 C++

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution
{
public:
    ListNode *Merge(ListNode *pHead1, ListNode *pHead2)
    {
        ListNode *head = new ListNode(0), *current = head;
        while (pHead1 && pHead2)
        {
            if (pHead1->val <= pHead2->val)
            {
                current->next = pHead1;
                pHead1 = pHead1->next;
            }
            else
            {
                current->next = pHead2;
                pHead2 = pHead2->next;
            }
            current = current->next;
        }
        current->next = pHead1 ? pHead1 : pHead2;
        return head->next;
    }
};

1.2.2 Java

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(0), current = head;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
        current.next = list1 != null ? list1 : list2;
        return head.next;
    }
}

2 解法二

使用递归完成上述过程，可以开辟新空间，也可以直接在原链表上修改。这里是直接在原链表上修改。

2.1 C++

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution
{
public:
    ListNode *Merge(ListNode *pHead1, ListNode *pHead2)
    {
        ListNode *head;
        if (pHead1 && pHead2)
        {
            if (pHead1->val <= pHead2->val)
            {
                head = pHead1;
                pHead1->next = Merge(pHead1->next, pHead2);
            }
            else
            {
                head = pHead2;
                pHead2->next = Merge(pHead2->next, pHead1);
            }
        }
        else
            head = pHead1 ? pHead1 : pHead2;
        return head;
    }
};

2.2 Java

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1, ListNode list2) {
        ListNode head;
        if (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                head = list1;
                list1.next = Merge(list1.next, list2);
            } else {
                head = list2;
                list2.next = Merge(list2.next, list1);
            }
        } else
            head = list1 != null ? list1 : list2;
        return head;
    }
}