206. 反转链表
描述
进阶
思路
- 迭代版本：利用二个指针，每次将node的后续节点保存在tmp中，然后将node指向pre，接着pre后移，node后移。
- 递归版本：和迭代版本的大体思路类似。其本质就是将pre=head; head=tmp; 两步变成了递归执行。
// 迭代版本
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. 合并两个有序链表
描述
- 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
- 输入：1->2->4, 1->3->4
- 输出：1->1->2->3->4->4
思路
- 因为链表是有序的，所以谁小谁加入新的列表上。
Tips
- 采用“指向头结点的节点”会省去很多冗余的代码，麻烦的条件判断。
- 链表不是数组，一旦链上了就全部串接上去了。
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，链表只要链上了就全串上了，不是数组。
if (l2 != NULL) pNode->next = l2;
return pHead->next;
}
};
