1. 反转链表

  1. //pre 指向前一个节点，cur 指向当前正在处理的节点，temp 暂存下一个节点
  3. ListNode* reverse(ListNode* head){
  4.     ListNode* pre = nullptr, *cur = head, *temp;
  5.     while(cur){
  6.         temp = cur->next;
  7.         cur->next = pre;
  8.         pre = cur;
  9.         cur = temp;
  10.     }
  11.     return pre;
  12. }
  1. ListNode* reverse(ListNode* head){
  2.     if (!head || !(head->next))
  3.         return head;
  4.     ListNode* newHead = reverse(head->next);
  5.     head->next->next = head;
  6.     head->next = nullptr
  7.     return newHead;
  8. }

2. 判断链表中是否存在环

  1. //快指针每次前进两个单位，慢指针每次前进一个单位,
  2. //如果链表中存在环则快慢指针一定会相遇 （尚不明白原理）
  4. bool hasCycle(ListNode *head) {
  5.     ListNode* slow, *fast;
  6.     slow = fast = head;
  8.     //没有环时快指针到达链表末尾
  9.     while(fast && fast->next){
  10.         fast = fast->next->next;
  11.         slow = slow->next;
  12.         if (fast == slow) return true;
  13.     }
  14.     return false;
  15. }
  1. //每次将当前节点的next指向自己，相当于从链表中删除自己，
  2. //如果最后遍历到了next指向自己的节点，则有两种可能：
  3. //1. 链表中原本就存在next指向自己的节点，判断为有环
  4. //2. 该节点是处理过后才指向自己，则代表有后面的节点指向前面的节点，判断为有环
  6. bool hasCycle(ListNode *head) {
  7.     ListNode* p = head, *next;
  9.     // p == nullptr 时表示链表无环
  10.     while(p){
  11.         //判断是否有环，同时如果判断成功则 p 为环的入口
  12.         if (p->next == p) return true;
  14.         //从链表中删除当前节点
  15.         next = p->next;
  16.         p->next = p;
  17.         p = next;
  18.     }
  19.     return false;
  20. }

3. 指出链表中环的起点

  1. //前半部分就是上面判断是否存在环的代码
  2. //判断存在环后，将快指针移至链表头，将快慢指针同时后移一位直至相遇,
  3. //该节点则为环的入口
  5. ListNode* EntryNodeOfLoop(ListNode* pHead) {
  6.     //快慢指针判断环，同上
  7.     ListNode* fast = pHead, *slow = pHead;
  8.     while(fast && fast->next){
  9.         fast = fast->next->next;
  10.         slow = slow->next;
  11.         if (fast == slow) break;
  12.     }
  14.     //不存在环的情况，注意还要判断 fast->next
  15.     if (!fast || !(fast->next)) return nullptr;
  17.     //寻找环的起点
  18.     fast = pHead;
  19.     while(fast != slow){
  20.         fast = fast->next;
  21.         slow = slow->next;
  22.     }
  23.     return fast;
  24. }

判断是否存在环中的逐个删除方法也可用来解此题，但实测效率不如快慢指针