本空逐弥 发表于 2021-7-24 17:32:32

C 两种解法觉得思路都正确，可只有一种可以通过

本帖最后由 本空逐弥 于 2021-7-24 17:40 编辑

问题是将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输入：1->2->4, 1->3->4输出：1->1->2->3->4->4 /** * Definition for singly-linked list. * struct ListNode { *   int val; *   struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){ }
正确的代码如下struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
    if(l1==NULL) return l2;
    if(l2==NULL) return l1;

    struct ListNode *ph, *pn, *pl1, *pl2;
    ph = NULL, pn = NULL, pl1 = l1, pl2 = l2;

    (pl1->val < pl2->val)?(ph=pl1,pl1=pl1->next):(ph=pl2,pl2=pl2->next);

    pn = ph;

    while(1){
      if(pl1 == NULL){
            pn->next = pl2;
            break;
      }
      if(pl2 == NULL){
            pn->next = pl1;
            break;
      }
      (pl1->val < pl2->val)?(pn->next=pl1,pl1 = pl1->next):(pn->next = pl2,pl2 = pl2->next);
      pn = pn->next;
    }

    return ph;
}

不能通过的代码如下struct ListNode* mergeTwolists(ListNode* l1, ListNode* l2) {
      ListNode *dummy ;
      ListNode *cur;
      dummy=(struct ListNode*)malloc(sizeof(struct ListNode);
      cur=dummy;
      while (l1 != NULL && l2 != NULL) {
            if (l1 -> val < l2 -> val) {
                cur -> next = l1;
                l1 = l1 -> next;
            }
            else {
                cur -> next = l2;
                l2 = l2 -> next;
            }
            cur = cur -> next;
      }
      cur -> next = (l1 != NULL ? l1 : l2);
      return dummy -> next;
    }觉得第二种简洁许多啊，怎么不能通过呢，输出没有反应。求各位大佬指教~

人造人 发表于 2021-7-24 19:31:41

看起来好像是没问题，把全部的代码贴出来，我动态调试一下看看

本空逐弥 发表于 2021-7-24 19:32:47

人造人 发表于 2021-7-24 19:31
看起来好像是没问题，把全部的代码贴出来，我动态调试一下看看

好

本空逐弥 发表于 2021-7-24 19:34:09

人造人 发表于 2021-7-24 19:31
看起来好像是没问题，把全部的代码贴出来，我动态调试一下看看

#include <stdio.h>
#include <malloc.h>
#define LEN sizeof(struct ListNode)

struct ListNode
{
      int val;
    struct ListNode *next;
};
int n;

struct ListNode*creat()
{
    struct ListNode*head;
    struct ListNode*p1,*p2;
    n=0;
    p1=p2=(struct ListNode*)malloc(LEN);
    scanf("%d",&p1->val);
    head=NULL;
    while(p1->val!=0)
    {
      n=n+1;
      if(n==1)head=p1;
      else p2->next=p1;
      p2=p1;
      p1=(struct ListNode*)malloc(LEN);
      scanf("%d",&p1->val);
    }
    p2->next=NULL;
    return(head);
}

struct ListNode* mergeTwolists(ListNode* l1, ListNode* l2) {
      ListNode *dummy ;
      ListNode *cur;
      dummy=(struct ListNode*)malloc(sizeof(struct ListNode);
      cur=dummy;
      while (l1 != NULL && l2 != NULL) {
            if (l1 -> val < l2 -> val) {
                cur -> next = l1;
                l1 = l1 -> next;
            }
            else {
                cur -> next = l2;
                l2 = l2 -> next;
            }
            cur = cur -> next;
      }
      cur -> next = (l1 != NULL ? l1 : l2);
      return dummy -> next;
    }


void print(struct ListNode*head)
{
    struct ListNode*p;
    p=head;
    if(head!=NULL)
      do
    {
      printf("%d ",p->val);
      p=p->next;
    }while(p!=NULL);
}

int main()
{
    struct ListNode *l1,*l2,*head;
    l1=creat();
    l2=creat();
    head=mergeTwoLists(l1,l2);
    print(head);
        return 0;
}

人造人 发表于 2021-7-24 20:23:02

3 个问题
1. 不要用C++环境学习C语言
2. 申请了内存要释放
3. 写错单词

#include <stdio.h>
#include <malloc.h>
#define LEN sizeof(struct ListNode)

struct ListNode
{
    int val;
    struct ListNode *next;
};

int n;

struct ListNode*creat()
{
    struct ListNode*head;
    struct ListNode*p1,*p2;
    n=0;
    p1=p2=(struct ListNode*)malloc(LEN);
    scanf("%d",&p1->val);
    head=NULL;
    while(p1->val!=0)
    {
      n=n+1;
      if(n==1)head=p1;
      else p2->next=p1;
      p2=p1;
      p1=(struct ListNode*)malloc(LEN);
      scanf("%d",&p1->val);
    }
    p2->next=NULL;
    return(head);
}

struct ListNode* mergeTwolists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *dummy ;
    struct ListNode *cur;
    dummy=(struct ListNode*)malloc(sizeof(struct ListNode));
    cur=dummy;
    while (l1 != NULL && l2 != NULL) {
      if (l1 -> val < l2 -> val) {
            cur -> next = l1;
            l1 = l1 -> next;
      }
      else {
            cur -> next = l2;
            l2 = l2 -> next;
      }
      cur = cur -> next;
    }
    cur -> next = (l1 != NULL ? l1 : l2);
    return dummy -> next;
}


void print(struct ListNode*head)
{
    struct ListNode*p;
    p=head;
    if(head!=NULL)
      do
      {
            printf("%d ",p->val);
            p=p->next;
      }while(p!=NULL);
}

int main()
{
    struct ListNode *l1,*l2,*head;
    l1=creat();
    l2=creat();
    //head=mergeTwoLists(l1,l2);
    head = mergeTwolists(l1, l2);
    print(head);
    return 0;
}

赚小钱 发表于 2021-7-25 00:45:14

两个问题，
第一，malloc 出来的 dummy 会返回一个没有数据，只有后继的头结点
第二，删除第二种写法的第15行
页: [1]
查看完整版本: C 两种解法觉得思路都正确，可只有一种可以通过