数据结构与算法之顺序表经典题目《合并两个有序数组》《合并两个有序链表》

《合并两个有序数组》习题是在学习线性表时的经典题目，可以使用顺序表和链表实现。这篇文章就是分别使用顺序表和链表进行实现。

1、合并两个有序数组

习题链接：合并两个有序数组

1.1、解题思路

1、首先创建三个变量：i，j，end。i用来记录nums1数组的下标，j用来记录nums2数组的下标，end用来存放每个数据元素的下标。这里我们从较大值开始比较，所以变量i和变量j的起始位置需要指向数组的末尾位置。所以可以如下定义：

int i = m-1;
int j = n-1;
int end = m+n-1;
1
2
3

如下图：

2、然后进行比较，无论是nums1[i] <= nums2[j]，还是nums1[i] > nums2[j]。我们就直接赋值，然后i- -、j- -和end- -。只不过不同的结果需要不同的赋值和不同的- -：

• 如果是nums1[i] > nums2[j]，就如下赋值：

  nums1[end] = nums1[i];
  end--;
  i--;
  1
  2
  3

• 如果是nums1[i] <= nums2[j]，就如下赋值：

  nums1[end] = nums2[j];
  end--;
  j--;
  1
  2
  3

• 最终的循环终止条件应该是两个数组只要有一个结束，循环就结束。

3、最后还有个特殊情况
就是合并结束后，会有一个数组有剩余，有可能是nums1，也有可能是nums2。
那这个时候我们只需要把剩余的数组的数据直接放在nums1数组后面即可。

1.2、代码展示

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int i = m-1;
    int j = n-1;
    int end = m+n-1;
    while(i>=0 && j>=0)
    {
        if (nums1[i] <= nums2[j])
        {
            nums1[end] = nums2[j];
            end--;
            j--;
        }
        else
        {
            nums1[end] = nums1[i];
            end--;
            i--;
        }
    }
    //考虑特殊情况
    while(j>=0)
    {
        nums1[end] = nums2[j];
        end--;
        j--;
    }

    while(i>=0)
    {
        nums1[end] = nums1[i];
        end--;
        i--;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

2、合并两个有序链表

习题链接：合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

2.1、解题思路

思路：依次比较链表中结点，每次取小的结点，尾插到新链表中即可。
1、首先判断list1和list2是否为NULL。如果list1为NULL，说明只有链表list2存在，那就不用合并了，直接返回list2即可。相同原理如果list2为NULL，链表list1存在，那就不用合并了，直接返回list1即可。
2、之后创建head和tail结点。并比较list1和list2结点的值，谁小就先链接谁即可。这里面有了点需要注意：第一次合并和不是第一次合并需要单独讨论。
3、最后就是那个链表还有剩余，就直接链接到需要合并的链表中即可。

2.2、代码实现

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }

    struct ListNode* head = NULL;
    struct ListNode* tail = NULL;
    while(list1 && list2)
    {
        //第一个链表的值<第二个链表的值的情况
        if (list1->val < list2->val)
        {
            //并且是第一次合并
            if (head == NULL)
            {
                head = tail = list1;
            }
            else
            {
                tail->next = list1;
                tail = list1;
            }
            list1 = list1->next;
        }
        //第一个链表的值>=第二个链表的值的情况
        else
        {
            if (head == NULL)
            {
                head = tail = list2;
            }
            else
            {
                tail->next = list2;
                tail = list2;
            }
            list2 = list2->next;
        }
    }

    //如果list2为NULL了，并且list1后面还有结点，就直接把list1后面的结点链接合并到大的链表后
    if (list1)
    {
        tail->next = list1; 
    }
     //如果list1为NULL了，并且list2后面还有结点，就直接把list2后面的结点链接合并到大的链表后
    if (list2)
    {
        tail->next = list2;
    }
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57