链表

链表具有以下性质：

在不考虑分页的情况下，顺序表逻辑上相邻的元素在物理上也相邻

异或链表

异或链表 (Xor Linked List) 也是一种链式存储结构，它可以降低空间复杂度达到和双向链表一样目的，任何一个节点可以方便的访问它的前驱节点和后继结点

题库

反转链表

输入一个链表，反转链表后，输出新链表的表头。

解题思路：使用双链表的方式：

/*
struct ListNode {
   int val;
   struct ListNode *next;
   ListNode(int x) :
         val(x), next(NULL) {
   }
};*/
class Solution {
public:
   ListNode* ReverseList(ListNode* pHead) {
      ListNode* bHead = nullptr;
      ListNode* cur = pHead;
      while(cur){
            ListNode* tmp = cur;
            cur = cur->next;
            tmp->next = bHead;
            bHead = tmp;
      }

      return bHead;
   }
};

判断是否有环

描述：

判断给定的链表中是否有环。如果有环则返回 true，否则返回 false。
你能给出空间复杂度 \(O(1)\) 的解法么？
输入分为 2 部分，第一部分为链表，第二部分代表是否有环，然后回组成 head 头结点传入到函数里面。-1 代表无环，其他的数字代表有环，这些参数解释仅仅是为了方便读者自测调试

按照牛客网的题解，可以使用快慢指针的方式：

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
   bool hasCycle(ListNode *head) {
      ListNode* fast = head;
      ListNode* low = head;
      while(low && fast){
            low = low->next;
            if(fast->next) fast = fast->next->next;
            else return false;
            if(low == fast) return true;
      }
      return false;
   }
};

当然了，每次走一步就向下迭代一次的方法也是可以的

单链表排序

给定一个无序单链表，实现单链表的排序 (按升序排序)。

使用插入排序，按照算法导论的思想，将链表分为无序的左手牌和有序的右手牌，每次从左手牌中抽出一张插入右手牌中

/**
* struct ListNode {
*    int val;
*    struct ListNode *next;
* };
*/

class Solution {
public:
   /**
   *
   * @param head ListNode类 the head node
   * @return ListNode类
   */
   ListNode* sortInList(ListNode* head) {
      ListNode* rhs = head;
      head = head->next;
      if(!head) return rhs;
      rhs->next = nullptr;
      while(head){
            auto pos = rhs;
            while(pos->next &&(head->val > pos->next->val) ) pos = pos->next;
            auto tmp = head;
            head = head->next;
            if(tmp->val < rhs->val){
               tmp->next = rhs;
               rhs = tmp;
               continue;
            }
            tmp->next = pos->next;
            pos->next = tmp;
      }
      return rhs;
   }
};

判断是否是回文链表

给定一个链表，请判断该链表是否为回文结构。

按照题解做的。首先用快慢指针将指针移动到链表的中点，然后对链表后半部分进行反转后与之前的链表进行比较。

/**
* struct ListNode {
*    int val;
*    struct ListNode *next;
* };
*/

class Solution {
public:
   /**
   *
   * @param head ListNode类 the head
   * @return bool布尔型
   */
   bool isPail(ListNode* head) {
      ListNode* fast = head;
      ListNode* low = head;
      while(fast && fast->next){
            fast = fast->next->next;
            low = low->next;
      }
      // 如果 fast != nullptr 说明链表的长度是奇数，这时 low->next 不用管
      if(fast) low = low->next;
      fast = ReverseList(low);
      low = head;
      while(fast){
            if(fast->val != low->val) return false;
            fast = fast->next;
            low = low->next;
      }
      return true;
   }
   static ListNode* ReverseList(ListNode* pHead) {
         ListNode* bHead = nullptr;
         ListNode* cur = pHead;
         while(cur){
               ListNode* tmp = cur;
               cur = cur->next;
               tmp->next = bHead;
               bHead = tmp;
         }
         return bHead;
      }
};

常数时间内删除单向链表节点

做三七互娱笔试题碰到的的，思想很简单，就是将下一个节点的值复制到当前节点，然后将下一个节点删除