SanfenR的博客

合并已经排序的2条链表(day11)

发表于 |

题目

  • 合并2条链表
    1
    如 1，3，5，7 和 2，4，6，8 -> 1,2,3,4,5,6,7,8

实现

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
ListNode * mergeList(ListNode* list1, ListNode* list2){
    if(!list1) return list2;
    if(!list2) return list1;
    ListNode* head;
    ListNode* tail = new ListNode();
    head = tail;
    while(list1 || list2) {
        if(!list2 || list1->value < list2->value) {
            tail->next = list1;
            tail=tail->next;
            list1=list1->next;
        } else {
            tail->next=list2;
            tail=tail->next;
            list2=list2->next;
        }
    }
    return head->next;
}
//使用递归
ListNode * mergeList2(ListNode* list1, ListNode* list2){
    if(!list1) return list2;
    if(!list2) return list1;
    ListNode* head;
    if(list1->value < list2->value){
        head = list1;
        head->next = mergeList2(list1->next, list2);
    }
    else{
        head = list2;
        head->next = mergeList2(list1,list2->next);
    }
    return head;
}

源码传送门