劍指 Offer 25. 合并兩個排序的鏈表

思路一：雙指針法

1.設(shè)置dummy為頭結(jié)點，放置于新鏈表之前，最后返回的就是dummy.next；設(shè)置cur為當前節(jié)點，從dummy開始
2.當兩個鏈表都非空時進入循環(huán)，令新鏈表的下一個節(jié)點cur.next為val更小的節(jié)點，相應(yīng)的鏈表節(jié)點后移一位
3.每次循環(huán)記得cur也要后移一位
4.如果循環(huán)結(jié)束后還有鏈表非空，cur指向非空鏈表
5.返回dummy.next

/*** 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) {ListNode* res = new ListNode(0); //新建一個頭節(jié)點ListNode* cur = res; //定義一個當前指針while(l1!=nullptr&&l2!=nullptr){if(l1->val<=l2->val){cur->next = l1;l1 = l1->next;}else {cur->next = l2;l2 = l2->next;}cur = cur->next;}/* if(l1==nullptr){cur->next = l2;}else if(l2==nullptr){cur->next = l1;}*/cur->next = l1!=nullptr? l1:l2;return res->next;} };

思路二：遞歸法

特判：如果有一個鏈表為空，返回另一個鏈表

如果l1節(jié)點值比l2小，下一個節(jié)點應(yīng)該是l1，應(yīng)該return l1，在return之前，指定l1的下一個節(jié)點應(yīng)該是l1.next和l2倆鏈表的合并后的頭結(jié)點

如果l1節(jié)點值比l2大，下一個節(jié)點應(yīng)該是l2，應(yīng)該return l2，在return之前，指定l2的下一個節(jié)點應(yīng)該是l1和l2.next倆鏈表的合并后的頭結(jié)點

/*** 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) {if(l1==nullptr) return l2;if(l2==nullptr) return l1;if(l1->val<=l2->val){l1->next = mergeTwoLists(l1->next, l2);return l1;}else{l2->next = mergeTwoLists(l1, l2->next);return l2;}} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode-剑指 Offer 25. 合并两个排序的链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。