Joyce' Blog
0%

merge-two-sorted-lists

发表于 更新于

题目表述

合并两个有序链表

解决方案

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
//将两个有序链表合并为一个新的有序链表并返回
//新链表是通过拼接给定的两个链表的所有节点组成的
/*
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
*/
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
	if (l1 == NULL)
		return l2;
	else if (l2 == NULL)
		return l1;
	ListNode *head, *tp, *t1, *t2;
	int m = l1->val, n = l2->val;
	t1 = l1;
	t2 = l2;
	if (m<n)
	{
		tp = new ListNode(m);
		t1 = l1->next;
	}
	else
	{
		tp = new ListNode(n);
		t2 = l2->next;
	}
	head = tp;
	while (t1&&t2)
	{
		m = t1->val, n = t2->val;
		if (m< n)
		{
			tp->next = new ListNode(m);
			tp = tp->next;
			t1 = t1->next;
		}
		else
		{
			tp->next = new ListNode(n);
			tp = tp->next;
			t2 = t2->next;
		}
	}
	if (t1)
		tp->next = t1;
	else if (t2)
		tp->next = t2;
	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
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == NULL)
        return l2;
    else if (l2 == NULL)
        return l1;
    ListNode *t1, *t2, *tmp;
    int n = l1->val, m = l2->val;
    if (n > m)
    {
        tmp = l1;
        l1 = l2;
        l2 = tmp;
    }
    t1 = l1;
    t2 = l2;
    while (t1&&t2)
    {
        ListNode *tmp1, *tmp2;
        n = t1->val, m = t2->val;
        if (n > m)
            while (t2->next&&t2->next->val <= n)
                t2 = t2->next;
        else if(n<m)
            while (t1->next&&t1->next->val <= m)
                t1 = t1->next;
        tmp1 = t1->next;
        t1->next = t2;
        t1 = t2;
        tmp2 = t2->next;
        if (t1 != NULL)
            t2->next = tmp1;
        else
            return l1;
        t2 = tmp2;
    }
    if (t2)
        t1 = t2;
    return l1;
}