链表问题（一）-LeetCode 138、382、203、143、141、142（有环链表入环节点，复制复杂链表）

• 2019 年 12 月 13 日
• 筆記

链表问题（一）：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