链表问题(一):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