链表问题（一）-LeetCode 138、382、203、143、141、142（有环链表入环节点，复制复杂链表）
链表问题（一）-LeetCode 138、382、203、143、141、142（有环链表入环节点，复制复杂链表）
链表问题（一）：LeetCode #138 382 203 143 141 142
1
编程题
【LeetCode #138】复制带随机指针的复杂链表
解题思路： 如图所示：
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head == nullptr) return nullptr;
Node* cur = head;
Node* pNext = nullptr;
// 第一步：1 -> 1' -> 2 -> 2' ...
while(cur != nullptr){
pNext = cur->next;
cur->next = new Node(cur->val);
cur->next->next = pNext;
cur = pNext;
}
// 第二步：修改random指针为cur->random->next
cur = head;
Node* copyNode = nullptr;
while(cur != nullptr){
pNext = cur->next->next;
copyNode = cur->next;
copyNode->random = ((cur->random == nullptr) ? nullptr : cur->random->next);
cur = pNext;
}
cur = head;
Node* res = cur->next;
while(cur != nullptr){
pNext = cur->next->next;
copyNode = cur->next;
cur->next = pNext;
copyNode->next = (pNext != nullptr) ? pNext->next : nullptr;
cur = pNext;
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer/
【LeetCode #382】链表的随机节点
给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。 进阶: 如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？
示例: // 初始化一个单链表 [1,2,3]. ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(3); Solution solution = new Solution(head); // getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。 solution.getRandom();
解题思路：
首先遍历得到链表的长度，然后使用rand函数获取随机值，在找到对应节点！
class Solution {
public:
/** @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node. */
Solution(ListNode* head) {
phead = head;
while(head != nullptr){
size++;
head = head->next;
}
}
/** Returns a random node's value. */
int getRandom() {
ListNode* cur = phead;
int k = rand() % size;
for(int i = ; i < k; i++){
cur = cur->next;
}
return cur->val;
}
private:
int size = ;
ListNode* phead;
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/linked-list-random-node
【LeetCode #203】移除链表元素
删除链表中等于给定值 val 的所有节点。
示例: 输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3->4->5
解题思路：
由于有可能是头结点被删除，因此需要使用哨兵节点dummy，在遍历删除中只使用一个指针pre，由于在循环中使用了pre->next->next, 因此while中的条件应该为pre->next != nullptr.
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummy = new ListNode(-1); // pre指向dummy节点
dummy->next = head;
ListNode* pre = dummy;
while(pre->next != nullptr){
if(pre->next->val == val){
pre->next = pre->next->next;
}else{
pre = pre->next;
}
}
return dummy->next;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/remove-linked-list-elements/
【LeetCode #143】重排链表
给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为：L0→Ln→L1→Ln-1→L2→Ln-2→… 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1: 给定链表 1->2->3->4, 重新排列为 1->4->2->3.
解题思路：
将每个节点的指针放入vector中，然后进行连接，直接原地O(1)太难了，我记不住。。。
class Solution {
public:
void reorderList(ListNode* head) {
if(head == nullptr) return;
vector<ListNode*> vec;
while(head != nullptr){
vec.push_back(head);
head = head->next;
}
int left = , right = vec.size()-1;
while(left < right){
vec[left]->next = vec[right];
vec[right--]->next = vec[++left];
}
vec[left]->next = nullptr;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reorder-list
【LeetCode #141】环形链表
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
示例 1： 输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
解题思路：
使用快慢指针，慢指针一次走一步，快指针一次走两步，如果有环，必定相遇，否则快指针会指向nullptr。
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == nullptr ||
head->next == nullptr ||
head->next->next == nullptr) return false; // 两个节点以上才会有环
ListNode *slow = head, *fast = head;
while(fast != nullptr){
slow = slow->next;
fast = (fast->next != nullptr) ? fast->next->next : nullptr;
if(slow == fast) return true;
}
return false;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/linked-list-cycle
【LeetCode #142】环形链表II
给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1： 输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。
解题思路：
仍然是快慢指针，快指针一次走两步，慢指针一次走一步，上一题只需要判断有环无环即可，因此只需要相遇一次就好了，但这一题需要返回入环节点，因此需要相遇两次！在第一次相遇后，将慢指针指向头部位置，同时快指针改为一次走一步，第二次相遇的节点即为入环节点！
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head == nullptr || head->next == nullptr ||
head->next->next == nullptr) return nullptr;
ListNode *slow = head, *fast = head;
while(fast != nullptr){
slow = slow->next;
fast = (fast->next != nullptr) ? fast->next->next : nullptr;
if(slow == fast){
break;
}
}
if(fast == nullptr) return nullptr;
slow = head;
while(slow != fast){
slow = slow->next;
fast = fast->next;
}
return slow;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/linked-list-cycle-ii