Leetcode 21 合并两个有序链表学习感悟

思路1：暴力迭代一个个往里面加

思路2：简单优化

//思路1： # include<iostream> # include<vector> # include<string> # include<algorithm> # include<math.h> # include<climits> # include<stack> using namespace std; struct ListNode { int val; ListNode* next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode* next) : val(x), next(next) {} }; ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* head = NULL; ListNode* p=head; ListNode* lp1 = l1; ListNode* lp2 = l2; while (lp1 || lp2) {//只要有一个节点存在 if (lp1 && lp2) { if (lp1->val < lp2->val) {//lp1数字小 l1 = lp1->next; if (!head) {//head开始为空 lp1->next = NULL;//断尾 head = lp1; lp1 = l1; p = head; } else {//head 已经不为空了 p->next = lp1; p = lp1; lp1 = l1; p->next = NULL; } } else {//lp2数字小 l2 = lp2->next; if (!head) {//head开始为空 lp2->next = NULL;//断尾 head = lp2; lp2 = l2; p = head; } else {//head 已经不为空了 p->next = lp2; p = lp2; lp2 = l2; p->next = NULL; } } } else if (!lp1) {//lp1不存在 if (!head) {//头不存在 head = l2; l2 = l2->next; p = head; } while (l2) { p->next = l2; p = p->next; l2 = l2->next; } lp2 = NULL; p->next = NULL; } else if (!lp2) {//lp2不存在 if (!head) {//头不存在 head = l1; l1 = l1->next; p = head; } while (l1) { p->next = l1; p = p->next; l1 = l1->next; } lp1 = NULL; p->next = NULL; } else { ; }//不可能出现 } return head; } int main(void) { ListNode* l1=new ListNode(1, new ListNode(2, new ListNode(4))); ListNode* l2=new ListNode(1, new ListNode(3, new ListNode(4)));; ListNode* head = mergeTwoLists(l1, l2); system("pause"); return 0; }

优化：

注意：l1,l2 在mergeTwoLists函数中是拷贝，所以在函数中将l1 , l2 信息丢失并不会影响原先的l1,l2 的链表数据

//思路2: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* head = new ListNode(-1); ListNode* p=head; while (l1 && l2) { if (l1->val < l2->val) {//l1小 p->next = l1; l1 = l1->next; } else { p->next = l2; l2 = l2->next; } p = p->next; } if (l1) p->next = l1; if (l2) p->next = l2; p = head; head = head->next; delete(p); return head; }