一道腾讯面试题，击败100%的用户，合并排序链表 - 哈喽比特

338次阅读 | 发布于3年以前

题目

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

示例1：

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 限制：

0 <= 链表长度 <= 1000

注意：本题与主站 21 题相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

文字思路

设置dummy为哑结点，放置于新链表之前，最后返回的就是dummy.next；设置cur为当前节点，从dummy开始
当两个链表都非空时进入循环，令新链表的下一个节点cur.next为val更小的节点，相应的链表节点后移一位
每次循环记得cur也要后移一位
如果循环结束后还有链表非空，cur指向非空链表
返回dummy.next

图解思路

上述图片中的文字：

创建一个伪头结点 tempHead 节点 cur 指向 tempHead 节点接下来比较 head1 和 head2 两个链表哪个节点小就把 tempHead 指向谁
head1.val >= head2.val 所以 head2 节点是值较小的，让cur.next指向head2节点
cur.next指向了head2，如图所示，接着让head2 = head2.next，让head2 继续参与接下来的比较。
完成了cur.next 指向了head2，head2 = head2.next，接下来让 cur指向下一个节点 cur = cur.next
完成了cur.next指向了head2，head2 = head2.next，cur = cur.next变成了如图所示。
接着继续重复上述过程继续比较 head1.val < head2.val
由于 head1.val < head2.val 继续执行之前的三步：cur.next = head1 head1 = head1.next cur = cur.next
由于 head1.val < head2.val 继续执行之前的三步：cur.next = head1 head1 = head1.next cur = cur.next 执行完这三步以后，如图所示。
接下来继续比较head1.val和head2.val 因为 head1.val < head2.val 继续执行之前的三步：cur.next = head1 head1 = head1.next cur = cur.next
cur.next = head1 head1 = head1.next cur = cur.next如图所示
接下来继续比较head1.val和 head2.val 因为 head1.val > head2.val：所以执行 cur.next = head2 head2 = head2.next cur = cur.next
接下来继续比较head1.val和 head2.val 因为 head1.val >= head2.val：所以继续执行 cur.next = head2 head2 = head2.next cur = cur.next
执行完如图所示，head1指向了null，所以排序列表一遍历结束了，所以把排序列表二接到合并排序列表后面。
接到后面，cur.next = head2 完成全部排序。
由于需要返回1-1-2-3-4-4 所以最后返回tempHead.next 节点

动画

代码

Java

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1 : l2;
        return dummy.next;
    }
}

JS

const mergeTwoLists = (l1, l2) => {
    // 定义一个虚拟节点，最后返回虚拟节点的下一个节点
    const res = new ListNode(0);
    // 定义p指向虚拟节点
    let p = res;
    // 定义p1,p2分别指向两个链表头部
    let [p1, p2] = [l1, l2];
    // 当p1, p2都有值的时候
    while (p1 && p2) {
        // 如果p1指向的值小，则p指向p1的值
        // p1右移
        // 否则p指向p2的值，p2右移
        if (p1.val < p2.val) {
            p.next = p1;
            p1 = p1.next;
        } else {
            p.next = p2;
            p2 = p2.next;
        }
        // 记得p也要右移
        p = p.next;
    }
    // 到最后退出循环了，p1,p2肯定有且只有一个是null
    // 那么另一个不是null的还没有连接到p上
    // 把p再连接到不是null的那个
    p.next = p1 ? p1 : p2;
    // 返回虚拟节点的下一个节点
    return res.next;
};

Python

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        res = ListNode(-1)
        p = res
        while l1 and l2:    
            if l1.val < l2.val:
                p.next = l1
                l1 = l1.next
            else:
                p.next = l2
                l2 = l2.next
            p = p.next
        p.next = l1 if l1 is not None else l2
        return res.next

C++

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* pHead = new ListNode(0);
        ListNode* pNode = pHead;
        while (l1 != NULL && l2 != NULL) {
            if (l1->val < l2->val) {
                pNode->next = l1;
                l1 = l1->next;
            }
            else {
                pNode->next = l2;
                l2 = l2->next;
            }
            pNode = pNode->next;
        }
        // 比较妙的一点在这里，就像归并排序一样最后要把没合并完的直接放进来，这里就不用遍历了，直接把节点挂上来就行
        if (l1)
            pNode->next = l1;
        else if (l2)
            pNode->next = l2;
        return pHead->next;
    }
};

Go


/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1==nil {return l2}
    if l2==nil {return l1}

    var n *ListNode
    if l1.Val<l2.Val {
        n = l1
        n.Next = mergeTwoLists(l1.Next,l2)
    } else {
        n = l2
        n.Next = mergeTwoLists(l1,l2.Next)
    }

    return n
}