1. 关键点

• 结点定义

//Definition for singly-linked list.
 struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

核心： 逆序思想
参考：https://blog.csdn.net/lycnjupt/article/details/47103433

循环过程如下：

next = head->next;
head->next = prev;
prev = head;
head = next;

初始条件为“` prev = NULL;
迭代停止条件为 head == NULL

2. 创建链表

ListNode* create()
{
    ListNode* pHead, *pNode, *temp;
    int x;
    pHead = pNode = (ListNode*)malloc(sizeof(ListNode));  //带头节点的链表
    // 先把第一个结点做了。
    printf("请输入链表数据，以小于0 的为结束标志：\n");
    scanf("%d", &x);
    pNode->val = x;
    pNode->next = NULL; 
    scanf("%d", &x);

    while (x>=0)
    {
        temp = (ListNode*)malloc(sizeof(ListNode));
        temp->val = x;
        temp->next = NULL;
        pNode->next = temp;//上一个结点指向当前新创建的结点
        pNode = temp;
        scanf("%d", &x);
    }
    pNode->next = nullptr;
    return pHead;
}

3. 实现逆序

ListNode* ReverseLink(LINK_NODE *head)
  {
       ListNode *next;
       ListNode *prev = NULL;
       while(head != NULL)
      {
          next = head->next;
          head->next = prev;
          prev = head;
          head = next;
      }
      return prev; //返回的是prev
   }

4. 判断回文

1 2 3 4 5 5 4 3 2 1 -> 是回文

同样借助上面的逆序的方法，采用龟兔算法
- 【234. Palindrome Linked List】
回文链表的特点就是对称，那么要判断是否回文就可以用两个指针指向对称的节点，看里面的信息是否一样。即对称的位置是否有对称的信息。由于是单向链表，不能同时用两个指针从头尾向内部遍历取值比较。那么就考虑从链表中间开始，用两个指针向两头遍历取值比较，显然这也需要进行链表逆置。

(1）. 获取链表的中点,使用龟兔算法的方法，两个指针，一个遍历速度是另外一个的两倍，找到中点
(2）. 然后反转链表的后半部分
(3）. 对比链表的前后两个部分是否一样
(4）. 最后将原链表的后半部分反转恢复原来的链表(恢复作案现场)

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true;
        ListNode *slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;//slow 每次移动一个
            fast = fast->next->next;//fast 每次移动2位
        }
        ListNode *last = slow->next, *pre = head;
        ListNode* prev = NULL;
        while (last != NULL) //这里就是前面的逆序部分
        {
            ListNode* tmp = last->next;
            last->next = prev;
            prev = last;
            last = tmp;
        }
        while (prev) //一一与正序的进行比较
        {
            if (prev->val != pre->val) 
                return false;//只要有不相等，提前结束
            prev = prev->next;
            pre = pre->next;
        }
        return true;
    }
};

5. 部分逆序

• 只翻转从m到n部分的链表
  Input: 1->2->3->4->5->NULL, m = 2, n = 4
  Output: 1->4->3->2->5->NULL

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        int L = 0;//total length
        ListNode* result = NULL;
        ListNode* pre = head;
        ListNode* prev = head;
        while (pre != NULL)
        {
            L++;
            pre = pre->next;//求总长度用
        }   
        if (m > n || m < 1 || n < 1 || m > L || n > L)
            return NULL; //不满足条件，返回NULL
        if (m == n)
            return head;// 不翻转
        for (int i = 1; i < m; i++)
            prev = prev->next;//此时的prev之后的需要逆转

        ListNode* result2 = head;
        ListNode* Next;
        ListNode* PreNode = NULL; //用来记录前一个结点
        ListNode* Now = prev; //需要反转的结点

        for (int i = m; i <= n; i++) //从m到n， 进行反转，与上面的逆序操作一样
        {
            Next = Now->next;
            Now->next = PreNode;//反转
            PreNode = Now;
            Now = Next;
        }

        int u = 1;
        ListNode* result3 = head;//最后要返回的结果保存
        while (u < m-1 && result2->next !=NULL)
        {
            u++;
            result2 = result2->next;//获取不变的第一部分
        }

        if (m == 1)
        {
            result3 = PreNode;//从第一个开始的话，就没有前面了部分了。
        }
        else
        {
            result2->next = NULL;
            result2->next = PreNode;//接上第二部分
        }

        ListNode* tmp2 = result3;
        u = 1;
        while (u < n )
        {
            tmp2 = tmp2->next;
            u++;
        }
        if (tmp2 != NULL)
            tmp2->next = Now;//接上第三部分
        return result3;
    }
};