########################################
链表
########################################

链表具有以下性质：

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

异或链表
****************************************

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

题库
****************************************

反转链表
========================================

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

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

.. code-block:: cpp

   /*
   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。

   你能给出空间复杂度 :math:`O(1)` 的解法么？

   输入分为 2 部分，第一部分为链表，第二部分代表是否有环，然后回组成 head 头结点传入到函数里面。-1 代表无环，其他的数字代表有环，这些参数解释仅仅是为了方便读者自测调试

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

.. code-block:: cpp

   /**
   * 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;
      }
   };

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

单链表排序
****************************************

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

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

.. code-block:: cpp

   /**
   * 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;
      }
   };

判断是否是回文链表
****************************************

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

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


.. code-block:: cpp

   /**
   * 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;
         }
   };

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

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