初级算法题（下）

初级算法题（下）

前接初级算法题（上）

链表

链表问题相对容易掌握。 不要忘记 “双指针解法” ，它不仅适用于数组问题，而且还适用于链表问题。

另一种大大简化链接列表问题的方法是 “Dummy node” 节点技巧 ，所谓 Dummy Node 其实就是带头节点的指针。

我们推荐以下题目：反转链表，合并两个有序链表和链接环。

更有额外的挑战，你可以尝试运用 递归 来解决这些问题：反转链表，回文链表和合并两个有序链表。

/*
* 链表部分习题，统一采用不带头结点的单链表结构
* 结构体定义如下
*/
//Definition for singly - linked list.
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) {}
};

3.01 删除链表的结点

请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。

题目数据保证需要删除的节点 不是末尾节点 。

示例 1：

输入：head = [4, 5, 1, 9], node = 5
输出：[4, 1, 9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

示例 2：

输入：head = [4, 5, 1, 9], node = 1
输出：[4, 5, 9]
解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9

// 替换法，测试通过
void deleteNode(ListNode* node) {node->val = node->next->val;node->next = node->next->next;
}

3.02 删除链表的倒数第N个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1, 2, 3, 4, 5], n = 2
输出：[1, 2, 3, 5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1, 2], n = 1
输出：[1]

// 方法一快慢指针，测试通过
// 首先建立一个头结点，方便后序编程
ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(0, head);ListNode* slow = dummy;ListNode* fast = head;for (int i = 0; i < n; ++i){fast = fast->next;}while (fast){fast = fast->next;slow = slow->next;}slow->next = slow->next->next;ListNode* ans = dummy->next;delete dummy;return ans;
}
// 方法二两次遍历法，测试通过
// 第一遍得到链表长度，第二遍删除结点
int getlength(ListNode* head)
{int count = 0;while (head){++count;head = head->next;}return count;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(0, head);int length = getlength(head);ListNode* ptr = dummy;for (int i = 1; i < length - n + 1; ++i){ptr = ptr->next;}ptr->next = ptr->next->next;ListNode* ans = dummy->next;delete dummy;return ans;
}
// 方法三堆栈法，测试通过
// 遍历链表，所有结点入栈，然后根据n值出栈
ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(0, head);stack<ListNode*> ms;ListNode* cur = dummy;while (cur){ms.push(cur);cur = cur->next;}for (int i = 0; i < n; ++i){ms.pop();}ListNode* prev = ms.top();prev->next = prev->next->next;ListNode* ans = dummy->next;delete dummy;return ans;
}
// 方法四快慢指针，测试通过
// 不建立头结点，使用了额外的一个指针指向待删除结点的前驱
ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* fast = head, * slow = head, * prev = head;for (int i = 0; i < n - 1; ++i){if (fast->next != NULL){fast = fast->next;}}while (fast->next != NULL){prev = slow;slow = slow->next;fast = fast->next;}if (slow == head) head = slow->next;else prev->next = slow->next;return head;
}

3.03 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1, 2, 3, 4, 5]
输出：[5, 4, 3, 2, 1]

示例 2：

输入：head = [1, 2]
输出：[2, 1]

示例 3：

输入：head = []
输出：[]

// 方法一迭代法，测试通过
// 这是没有使用头结点的方法，使用了三个指针完成
ListNode* reverseList(ListNode* head) {if (head == nullptr) return nullptr;ListNode* first = head;if (first->next == nullptr) return head;ListNode* second = first->next;ListNode* third;if (second->next != nullptr) third = second->next;first->next = nullptr;while (third != nullptr){second->next = first;first = second;second = third;third = third->next;}second->next = first;first = second;return first;
}
// 方法二迭代法，测试通过
// 方法一的改进版本，使用了更少的指针，减少了代码量
ListNode* reverseList(ListNode* head) {if (head == nullptr || head->next == nullptr) return head;ListNode* p = head;head = nullptr;while (p != nullptr){ListNode* s = p;p = p->next;s->next = head;head = s;}return head;
}
// 方法三迭代法，测试通过
// 首先构造了头结点，然后按照有头结点的单链表进行逆置
ListNode* reverseList(ListNode* head) {ListNode* truehead = new ListNode(-1, head);ListNode* p = truehead->next;truehead->next = nullptr;while (p != nullptr){ListNode* s = p;p = p->next;s->next = truehead->next;truehead->next = s;}return truehead->next;
}
// 方法四递归法，测试通过
// 基本思路是递归进入最后一个结点，然后再回归的时候逆接所有结点。较难理解，不建议采用
ListNode* reverse(ListNode* pre, ListNode* p)
{ListNode* tail = nullptr;if (p != nullptr){tail = reverse(p, p->next);p->next = pre;}else{tail = pre;}return tail;
}
ListNode* reverseList(ListNode* head) {if (head == nullptr || head->next == nullptr) return head;return reverse(nullptr, head);
}

3.04 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1, 2, 4], l2 = [1, 3, 4]
输出：[1, 1, 2, 3, 4, 4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

// 方法一迭代法，测试通过
// 没有使用额外结点，直接在原链表进行操作，缺点是使用指针较多，代码不简洁
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (list1 == nullptr || list2 == nullptr){if (list1 == nullptr) return list2;else return list1;}ListNode* p1 = list1;ListNode* p2 = list2;ListNode* list3 = p1->val < p2->val ? p1 : p2;ListNode* p3 = list3;if (list3 == p1) p1 = p1->next;else p2 = p2->next;while (p1 != nullptr && p2 != nullptr){if (p1->val < p2->val){p3->next = p1;p3 = p1;p1 = p1->next;}else{p3->next = p2;p3 = p2;p2 = p2->next;}}if (p1 == nullptr){p3->next = p2;}else{p3->next = p1;}return list3;
}
// 方法二迭代法，测试通过
// 继方法一的优化版本，使用了一个额外结点作为开始头结点，然后思路同方法一
// 代码简洁同时易于理解，建议采用
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* mergelist = new ListNode(-1);ListNode* prev = mergelist;while (list1 != nullptr && list2 != nullptr){if (list1->val < list2->val){prev->next = list1;list1 = list1->next;}else{prev->next = list2;list2 = list2->next;}prev = prev->next;}prev->next = list1 == nullptr ? list2 : list1;return mergelist->next;
}
// 方法三递归法，测试通过
// 基本思想如下：
// list1[0] + merge(list1[1:], list2)--list1[0] < list2[0]
// list2[0] + merge(list1, list2[1:])--otherwise
// 也就是说，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。
// 在此思想的基础上加入边界条件判断，及空结点的情况
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (list1 == nullptr){return list2;}else if (list2 == nullptr){return list1;}else if (list1->val < list2->val){list1->next = mergeTwoLists(list1->next, list2);return list1;}else{list2->next = mergeTwoLists(list1, list2->next);return list2;}
}

3.05 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1, 2, 2, 1]
输出：true

示例 2：

输入：head = [1, 2]
输出：false

// 方法一部分反转法，测试通过
// 通过快慢指针找到链表的中点，然后将中点之后的链表反转，前半部分和后半部分进行比较看是否相等
// 注意：调用了之前反转链表的方法
bool isPalindrome(ListNode* head) {ListNode* fast = head;ListNode* slow = head;while (fast != nullptr && fast->next != nullptr){fast = fast->next->next;slow = slow->next;}slow = reverseList(slow);// 调用 反转链表 方法while (slow != nullptr){if (slow->val != head->val) return false;slow = slow->next;head = head->next;}return true;
}
// 方法二堆栈法，测试通过
// 使用栈后进先出的特性，首先将链表中的元素入栈，然后从链表头部开始依次和栈顶元素进行比较，
// 不需要将链表所有元素再比较一遍，只需要比较前一半元素即可
bool isPalindrome(ListNode* head) {stack<ListNode*> stk;ListNode* p = head;int len = 0;while (p != nullptr){stk.push(p);p = p->next;len++;}len >>= 1;for (int i = 0; i < len; ++i){if (head->val == p()->val){stk.pop();head = head->next;}else return false;}return true;
}
// 方法三递归法，测试通过
// 基本思路是使用两个指针，一个从前往后走，一个从后往前走，依次比较元素是否相等
// 由于单链表无法直接从后向前遍历，但是利用递归一定会进行回归的特性可以在逻辑上
// 做到从后向前的递归。同时注意，前向指针需要进行外部定义，不受到函数调用栈的影响
ListNode* frontnode;// 外部定义指针
bool recursive(ListNode* currentNode) {if (currentNode != nullptr){if (!recursive(currentNode->next)) return false;if (frontnode->val != currentNode->val) return false;frontnode = frontnode->next;}return true;
}
bool isPalindrome(ListNode* head) {frontnode = head;return recursive(head);
}

3.06 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3, 2, 0, -