夯实C++基础之刷题：链表——3合并两个有序列表

题目

解题（递归和迭代

我的理解：递归是自己调用自己，迭代是按思路往下走
1、递归

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        //递归
        if(list1 == NULL) return list2;
        else if(list2 == NULL) return list1;
        else if(list1->val < list2->val)
        {
            //想不清楚的话就假设此时list1只有一个元素，那这一个元素指向list2，且返回list1
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }else{
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

2、迭代
定义两个指针，一个头节点，一个节点指向下一个节点

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head = new ListNode(-1);
        ListNode* cur = head;
        while(list1!=NULL && list2!=NULL)
        {
            if(list1->val < list2->val)
            {
                cur->next = list1;
                list1 = list1->next;
            }
            else
           {
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;//这一步不能忘了，自己也要往下走哇
        }
        //最后最多只有一个是空
        cur->next = list1==NULL?list2:list1;
        return head->next;
    }
};