【EASY】Merge Two Sorted Lists

发布于: 2018-12-20 22:16
阅读: 44
评论: 0
喜欢: 0

问题

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

分析过程

  • 输入:两个有序的链表
  • 输出:合成一整个链表
  • 思路:新建一个根节点,然后按次序扫描两个链表,重新挂接链表。

解决方法

class Node {
public:
    int val;
    Node *next;
    
    Node(int val) {
        this->val = val;
        this->next = nullptr;
    }
    
    Node *copy() {
        return new Node(val);
    }
};

Node *mergeSortedLists(Node *listA, Node *listB) {
    if (!listA || !listB) {
        return listA ?: listB;
    }
    
    Node *tmpA = listA, *tmpB = listB;
    // 新建一个根节点用于往后挂接
    Node newList = Node(0);
    // 正在挂接的节点
    Node *tmp = &newList;
    
    while (tmpA && tmpB) {
        if (tmpA->val <= tmpB->val) {
            tmp->next = tmpA;
            tmpA = tmpA->next;
        } else {
            tmp->next = tmpB;
            tmpB = tmpB->next;
        }
        tmp = tmp->next;
    }
    // 其中一个链表空了,此时把另一个挂上去
    tmp->next = tmpA ?: tmpB;
    
    return newList.next;
}

int main() {
    
    Node *n1 = new Node(1);
    Node *n2 = new Node(2);
    Node *n3 = new Node(4);
    Node *n4 = new Node(1);
    Node *n5 = new Node(3);
    Node *n6 = new Node(4);
    
    n1->next = n2;
    n2->next = n3;
    
    n4->next = n5;
    n5->next = n6;
    
    // 1->2->4
    Node *listA = n1;
    // 1->3->4
    Node *listB = n4;
    
    Node *newList = mergeSortedLists(listA, listB);
    
    return 0;
}

Thanks for reading.

All the best wishes for you! 💕