Q*******e
发帖数: 939 | 1 抛砖引玉,
struct list_node *
merge2sorted2(struct list_node *a, struct list_node *b)
{
int first_node;
struct list_node *head = NULL;
struct list_node *cur = NULL, *node;
if (a == NULL) return b;
if (b == NULL) return a;
first_node = 1;
while (a || b ) {
if (a && b) {
if (a->data < b->data) {
node = a;
a = a->next;
} else {
node = b;
b = b->next;
}
} else if (a) {
node = a;
a = a->next;
} else {
node = b;
b = b->next;
}
if (first_node) {
head = node;
cur = node;
first_node = 0;
} else {
cur->next = node;
cur = cur->next;
}
}
return head;
} | b***m
发帖数: 5987 | 2 这个还能多优？
【在 Q*******e 的大作中提到】
: 抛砖引玉,
: struct list_node *
: merge2sorted2(struct list_node *a, struct list_node *b)
: {
: int first_node;
: struct list_node *head = NULL;
: struct list_node *cur = NULL, *node;
: if (a == NULL) return b;
: if (b == NULL) return a;
: first_node = 1;
| c*****a
发帖数: 808 | | h****n
发帖数: 1093 | | h****n
发帖数: 1093 | 5 写了三个方法，一个是递归，一个是naive方法，一个是用指向指针的指针来构建
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
ListNode* res;
//Method using pointer to pointer
res = P2PMethod(l1,l2);
//res = recursive(l1,l2);
//res = naiveMethod(l1,l2);
return res;
}
ListNode* naiveMethod(ListNode *l1, ListNode *l2)
{
if(l1==NULL&&l2==NULL) return NULL;
if(l1==NULL) return l2;
if(l2==NULL) return l1;
ListNode * curP1 = l1;
ListNode * curP2 = l2;
ListNode newHead(0);
ListNode * cur= &newHead;
while(curP1&&curP2)
{
if(curP1->valval)
{
cur->next = curP1;
curP1 = curP1->next;
}
else
{
cur->next = curP2;
curP2 = curP2->next;
}
cur = cur->next;
}
if(curP1||curP2)
{
while(curP1)
{
cur->next = curP1;
curP1=curP1->next;
cur = cur->next;
}
while(curP2)
{
cur->next = curP2;
curP2=curP2->next;
cur = cur->next;
}
}
cur->next = NULL;
return newHead.next;
}
ListNode* recursive(ListNode *l1, ListNode *l2)
{
if(l1==NULL&&l2==NULL) return NULL;
if(l1==NULL) return l2;
if(l2==NULL) return l1;
if(l1->valval)
{
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
else
{
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
ListNode* P2PMethod(ListNode *l1, ListNode *l2)
{
ListNode* res;
ListNode** resp = &res;
while(l1||l2)
{
if(l1&&l2)
{
if(l1->val>l2->val)
{
*resp = l2;
resp = &(l2->next);
l2 = l2->next;
}
else
{
*resp = l1;
resp = &(l1->next);
l1 = l1->next;
}
}
else if(l1)
{
*resp = l1;
resp = &(l1->next);
l1 = l1->next;
}
else
{
*resp = l2;
resp = &(l2->next);
l2 = l2->next;
}
}
*resp = NULL;
return res;
}
}; |
|
