Merge Two Sorted Lists-满满的套路

青旅半醒 2022-07-18 01:07 66阅读 0赞

# leetcode-21 #

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

# 不带头结点的版本 #

## 实现 ##

/**
     1. Definition for singly-linked list.
     2. struct ListNode {
     3.     int val;
     4.     ListNode *next;
     5.     ListNode(int x) : val(x), next(NULL) {}
     6. };
     */
    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            ListNode *head = NULL;
            ListNode *tmp = NULL, *cur = NULL;
            while (l1 && l2) {
                if (l1->val < l2->val) {
                    tmp = l1;
                    l1 = l1->next;
                } else {
                    tmp = l2;
                    l2 = l2->next;
                }
                if (!head) { 
                    cur = tmp;
                    head = cur;
                } else {
                    cur->next = tmp;
                    cur = cur->next;
                }
            }
            if (l1) {
                if (!head)
                    head = l1;
                else 
                    cur->next = l1;
            }
            if (l2) {
                if (!head)
                    head = l2;
                else
                    cur->next = l2;
            }
    
            return head;
        }
    };

## 分析 ##

1.  两个链表合并，合并后的新链表的`头结点不定`，这里定义 head 指针指向合并后新链表的头结点。
2.  使用cur指针指向合并后新链表的当前节点。
3.  新链表的`头结点不定`，合并时必须考虑如何确定新链表的头指针。
4.  因此，上述代码比较复杂，容易出错，而且并不适合应试。

# 带头结点的版本 #

## 代码 ##

class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            // 创建一个头结点
            ListNode *head = new ListNode(0);
            ListNode *cur = head;
            while (l1 && l2) {
                if (l1->val < l2->val) {
                    cur->next = l1;
                    l1 = l1->next;
                } else {
                    cur->next = l2;
                    l2 = l2->next;
                }
                cur = cur->next;
            }
    
            cur->next = l1 ? l1 : l2;
            return head->next;
        }
    };

## 分析 ##

1.  给合并的新链表创建一个头结点，这个头结点作用就是避免`合并后新链表头指针无法确定指向哪个节点的问题`
2.  新链表使用cur指针指向头结点
3.  `cur->next指针`指向每次加入到新链表的节点
4.  更新新链表的cur指针 `cur = cur->next`
5.  跳出while循环后，判断哪一个链表遍历不为空，更新cur->next值为不为空的链表
6.  返回head->next即为合并后新链表

## 优点 ##

`不带头结点和带头结点版本`对比：

1 新链表头头指针带来的问题：  
在合并两个排序链表的问题中，新链表创建必须`确定新链表的头结点`。  
新链表头指针指向哪个链表中第一个插入到新链表节点由比较结果确定。

2 带头结点的新链表避免头指针不确定的问题：  
带头结点的新链表中，只需要把比较中胜出的节点插入到新链表的尾部，即普通的链表尾部插入问题。

通过以上分析，在遇到新链表头指针不确定问题时可以使用创建头结点的方式简化创建新链表的过程，满满的套路。

# 参考 #

[Merge Two Sorted Lists][]

[Merge Two Sorted Lists]: http://algorithm.yuanbin.me/zh-hans/linked_list/merge_two_sorted_lists.html