206. 反轉(zhuǎn)鏈表
描述
進(jìn)階
- 鏈表可以迭代或遞歸地反轉(zhuǎn)。你能否兩個都實(shí)現(xiàn)一遍胆敞？
思路
- 迭代版本：利用二個指針，每次將node的后續(xù)節(jié)點(diǎn)保存在tmp中杂伟，然后將node指向pre移层，接著pre后移，node后移赫粥。
- 遞歸版本：和迭代版本的大體思路類似观话。其本質(zhì)就是將pre=head; head=tmp; 兩步變成了遞歸執(zhí)行。
// 迭代版本
class Solution_206_01 {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL) return NULL;
ListNode* pre = NULL;
while (head) {
ListNode* tmp = head->next;
head->next = pre;
pre = head;
head = tmp;
}
return pre;
}
};
class Solution_206_02 {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL) return NULL;
ListNode* pre = NULL;
return RecurReverse(pre, head);
}
ListNode* RecurReverse(ListNode* pre, ListNode* node) {
if (node) {
ListNode* tmp = node->next;
node->next = pre;
return RecurReverse(node, tmp);
}
return pre;
}
};
21. 合并兩個有序鏈表
描述
- 將兩個有序鏈表合并為一個新的有序鏈表并返回越平。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點(diǎn)組成的频蛔。
示例
- 輸入：1->2->4, 1->3->4
- 輸出：1->1->2->3->4->4
思路
- 因?yàn)殒湵硎怯行虻模哉l小誰加入新的列表上喧笔。
Tips
- 采用“指向頭結(jié)點(diǎn)的節(jié)點(diǎn)”會省去很多冗余的代碼帽驯，麻煩的條件判斷龟再。
- 鏈表不是數(shù)組书闸，一旦鏈上了就全部串接上去了。
class Solution_21 {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL && l2 == NULL) return NULL;
ListNode* pHead = new ListNode(0);
ListNode* pNode = pHead;
while (l1 && l2) {
if (l1->val < l2->val) {
pNode->next = l1;
l1 = l1->next;
} else {
pNode->next = l2;
l2 = l2->next;
}
pNode = pNode->next;
}
if (l1 != NULL) pNode->next = l1; // 這里不需要用while利凑，鏈表只要鏈上了就全串上了浆劲，不是數(shù)組。
if (l2 != NULL) pNode->next = l2;
return pHead->next;
}
};
