-
Notifications
You must be signed in to change notification settings - Fork 34
/
Merge_Two_Sorted_Lists.cpp
60 lines (55 loc) · 1.19 KB
/
Merge_Two_Sorted_Lists.cpp
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
/*
Author: Weixian Zhou, ideazwx@gmail.com
Date: Jul 7, 2012
Problem: Merge Two Sorted Lists
Difficulty: easy
Source: http://www.leetcode.com/onlinejudge
Notes:
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.
Solution:
*/
#include <vector>
#include <set>
#include <climits>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstring>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode *head = NULL;
ListNode *tail = NULL;
ListNode **next_list = NULL;
while (l1 != NULL && l2 != NULL) {
next_list = (l1->val < l2->val ? &l1 : &l2);
if (head == NULL) {
head = *next_list;
tail = *next_list;
} else {
tail->next = *next_list;
tail = tail->next;
}
*next_list = (*next_list)->next;
}
next_list = (l1 != NULL ? &l1 : &l2);
if (next_list != NULL) {
if (head == NULL) {
head = *next_list;
} else {
tail->next = *next_list;
}
}
return head;
}
};