首页 > 代码库 > leetcode链表--8、merge-two-sorted-list(按顺序合并两个已经排好序的链表)
leetcode链表--8、merge-two-sorted-list(按顺序合并两个已经排好序的链表)
题目描述
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.
解题思路:
1)定义l,每次l指向两个链表中小的那个节点,定义head为头指针,定义ptr,将l依次连成链表
2)两个链表均不为空,将其小的值赋给l
3)将其中节点多的那个链表剩余节点赋给l
4)每次l得到赋值后,ptr = l;ptr=ptr->next,连成新链表
1 #include <iostream> 2 #include <malloc.h> 3 using namespace std; 4 struct ListNode { 5 int val; 6 ListNode *next; 7 ListNode(int x) : val(x), next(NULL) {} 8 }; 9 /*-----------------------------创建链表(不带头结点)---------------------------------*/ 10 /*在链表的末端插入新的节点,建立链表*/ 11 ListNode *CreateList(int n) 12 { 13 ListNode *head;//指向头结点指针 14 ListNode *p,*pre; 15 int i; 16 head=(ListNode *)malloc(sizeof(ListNode));//为头节点分配内存空间 17 head->next=NULL;//将头结点的指针域清空 18 pre=head;//先将头结点首地址赋给中间变量pre 19 for(i=1;i<=n;i++)//通过for循环不断加入新的结点 20 { 21 p=(ListNode *)malloc(sizeof(ListNode));//为要插入的节点分配 22 //内存空间p指向新插入结点的首地址 23 cin>>p->val;//输入数值 24 pre->next=p;//将p指向新结点插入链表也就是头结点指针域指向 25 //下个结点 26 //第一个结点就是p指向的,因为头结点内容为空 27 pre=p;//这个起着指向下一个结点的作用 等价于pre=pre->next 28 } 29 p->next=NULL;//最后将最后一个结点的指针域清空了 30 31 return head->next;//不带空的头结点 32 } 33 /*-------------------------输出链表-----------------------------------*/ 34 void PrintList(ListNode *h) 35 { 36 ListNode *p; 37 38 p=h;//不带空的头结点 39 while(p) 40 { 41 cout<<p->val<<" "; 42 p=p->next; 43 cout<<endl; 44 } 45 } 46 class Solution { 47 public: 48 ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { 49 int n1 = 0; 50 int n2 = 0; 51 ListNode * head = new ListNode(0); 52 ListNode * ptr = head; 53 ListNode *l = l1; 54 while(l1 != NULL && l2 != NULL) 55 { 56 if(l1->val <= l2->val) 57 { 58 l = l1; 59 l1 = l1->next; 60 61 } 62 else 63 { 64 l = l2; 65 l2 = l2->next; 66 } 67 ptr->next = l; 68 ptr = ptr->next; 69 } 70 while(l1 != NULL) 71 { 72 l = l1; 73 l1 = l1->next; 74 ptr->next = l; 75 ptr = ptr->next; 76 } 77 while(l2 != NULL) 78 { 79 l = l2; 80 l2 = l2->next; 81 ptr->next = l; 82 ptr = ptr->next; 83 } 84 return head->next; 85 } 86 }; 87 int main() 88 { 89 int n1; 90 int n2; 91 ListNode *h1; 92 ListNode *h2; 93 ListNode *h; 94 cout<<"输入链表1的结点数目"<<endl; 95 cin>>n1; 96 h1 = CreateList(n1); 97 cout<<"链表1为:"<<endl; 98 PrintList(h1); 99 cout<<"输入链表2的结点数目"<<endl; 100 cin>>n2; 101 h2 = CreateList(n2); 102 cout<<"链表2为:"<<endl; 103 PrintList(h2); 104 Solution s; 105 h = s.mergeTwoLists(h1,h2); 106 cout<<"合并后链表为: "<<endl; 107 PrintList(h); 108 109 return 0; 110 }
正常情况运行结果截图:
两个链表均为空:
一个链表为空:
leetcode链表--8、merge-two-sorted-list(按顺序合并两个已经排好序的链表)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。