234. 回文链表

描述

• 请检查一个链表是否为回文链表。

进阶

• 你能在 O(n) 的时间和 O(1) 的额外空间中做到吗？

思路

1. 所谓回文链表即对折以后相等，使用头尾两个指针，依次向中间靠就好了。
2. 难点在于这个是个单向链表，所以找到尾指针和向前移动是算法的难点。
3. 尾指针可以通过一次遍历定位到。向前移动则没那么好解决。
4. 思路一：采用空间换时间，构建一个新的reverse后的链表，然后对比两个链表是否相等。空间复杂度O(n)
5. 思路二：思路一的方法之所以需要构建一个新的链表，是害怕破坏了原有链表的结构，导致后续无法一一比对。但其实并不需要比对整个链表，只需比对前半段和后半段就可以了。所以核心思路是找到后半段，翻转，然后和前半段进行比较。

Tips

1. 反转链表运用一个临时节点保存next节点。
2. findMid则运用快慢两个指针来完成。

class Solution_234_01 {
 public:
  bool isPalindrome(ListNode* head) {
    if (head == NULL) return true;
    ListNode* rHead = new ListNode(0);
    ListNode* tmp = head;
    ListNode* rTmp = rHead;
    while (tmp) {
      rTmp->next = new ListNode(tmp->val);
      tmp = tmp->next;
      rTmp = rTmp->next;
    }
    rHead = rHead->next;
    rHead = reverseList(rHead);
    while (head && rHead) {
      if (head->val != rHead->val) return false;
      head = head->next;
      rHead = rHead->next;
    }
    return true;
  }
  ListNode* reverseList(ListNode* head) {
    ListNode* pre = NULL;
    while (head) {
      ListNode* tmp = head->next;
      head->next = pre;
      pre = head;
      head = tmp;
    }
    return pre;
  }
};

class Solution_234_02 {
 public:
  bool isPalindrome(ListNode* head) {
    if (head == NULL) return true;
    ListNode* mid = findMid(head);
    mid = reverseList(mid->next);
    while (head && mid) {
      if (head->val != mid->val) return false;
      head = head->next;
      mid = mid->next;
    }
    return true;
  }
  ListNode* findMid(ListNode* head) {
    ListNode* slow = head;        // slow走一步到head
    ListNode* fast = slow->next;  // fast走两步到head->next
    while (fast && fast->next) {
      slow = slow->next;
      fast = fast->next->next;
    }
    return slow;
  }
  ListNode* reverseList(ListNode* head) {
    ListNode* pre = NULL;
    while (head) {
      ListNode* tmp = head->next;
      head->next = pre;
      pre = head;
      head = tmp;
    }
    return pre;
  }
};

141. 环形链表

描述

• 给定一个链表，判断链表中是否有环。

进阶

• 你能否不使用额外空间解决此题？

思路

1. 和findMid的思路类型，如果链表中有环，则快指针一定能追上满指针。

class Solution {
 public:
  bool hasCycle(ListNode* head) {
    if (head == NULL) return false;
    ListNode* slow = head;
    ListNode* fast = slow->next;
    if (slow == fast) return true;
    while (fast && fast->next) {
      // 这里不用额外考虑“跑过头”的问题，如果跑过头，则上一个节点就已经相遇了
      if (slow == fast) return true; // 其实仔细思考，两指针每次距离缩短1，所以不会存在跑过头的问题
      slow = slow->next;
      fast = fast->next->next;
    }
    return false;
  }
};