发表更新数据结构与算法3 分钟读完 (大约389个字)

【leetcode】21. Merge Two Sorted Lists

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

题目属于简单类型，但是好久没写这种题了，再加上C语言也很久没写过了，费了很久。。。
思路很简单，先以一个为基准，然后再将另外一个逐个插入其中（然而开始的时候并不是这么想的，用的某种骚操作，结果发现写着写着搞不定了，这种写代码的方式果然不行呀）。感觉还可以有提高的地方，比如用个二分什么的。

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
#define FINISHED -1
#define UNFINISHED -2
#define SKIP 0
void showList(struct ListNode* l) {
    printf("[");
    while (l != NULL) {
        printf("%d", l->val);
        if (l->next != NULL) {
            printf(",");
        }
        l = l->next;
    }
    printf("]\n");
}

int insertNode(struct ListNode* l, struct ListNode* node) {
    struct ListNode* tmp;
    struct ListNode* pre = NULL;
    struct ListNode* tp = l;
    int handled = 0;
    // printf("Before insert: ");showList(l);
    while (tp != NULL) {
        // printf("tp->val = %d, node->val = %d\n", tp->val, node->val);
        if (node->val <= tp->val) {
            if (tp == l) {
                int ti = l->val;
                l->val = node->val;
                node->val = ti;
                
                tmp = l->next;
                l->next = node;
                node->next = tmp;
            } else {
                pre->next = node;
                node = node->next;
                pre->next->next = tp;
            }
            handled = 1;
            break;
        }
        pre = tp;
        tp = tp->next;
    }
    if (!handled) {
        pre->next = node;
        return FINISHED;
    }
    // printf("After insert: ");showList(l);
    return UNFINISHED;
}

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
	struct ListNode* root = NULL;
	
    if (l1 == NULL || l2 == NULL) {
        if (root == NULL)
            root = (l1 == NULL ? l2 : l1);
        return root;
    }
    if (root == NULL) {
        root = l1;
    }
    l1 = l2;
    int finished = UNFINISHED;
    while (l1 != NULL) {
        struct ListNode* next = l1->next;
        int res = insertNode(root, l1);
        switch(res){
            case FINISHED: return root;
            case UNFINISHED: 
            case SKIP: 
                l1 = next;
                break;
        }
        // printf("Wait to insert: ");showList(l1);
    }
	return root;
}

归档

最新文章

链接

×