竭力履行你的义务，你应该就会知道，你到底有多大的价值。      --列夫.托尔斯泰

目录

🪴一.回文链表

🌻1.快慢指针 

🍁2.把值存入数组中，然后使用双指针 

🌼二.交换链表中的结点 

🍂1.快慢指针

🪴一.回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：

输入：head = [1,2,2,1]
输出：true

 示例 2：

输入：head = [1,2]
输出：false

提示：

• 链表中节点数目在范围[1, 105] 内
• 0 <= Node.val <= 9

 做题链接：回文链表

🌻1.快慢指针 

快慢指针就是一个快指针走两步，另一个慢指针走一步，当快指针走到尾的时候，慢指针走到中间结点的位置。然后我们把慢指针后面的结点全部反转，然后和前面没反转的链表遍历比较，如果有不相等的结点值，那么该链表就不是回文链表，反之，就是回文链表。

这题其实就是之前我们学的反转链表和找链表中间结点的结合版。我们还是通过画图来理解一下。

有了这个思路，写起代码来也就得心应手了。

//找中间结点
struct ListNode*midhead(struct ListNode*head)
{
    struct ListNode*fast=head;
    struct ListNode*slow=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

//反转链表
struct ListNode*reverselink(struct ListNode*mid)
{
    struct ListNode*phead=NULL;
    while(mid)
    {
        struct ListNode*next=mid->next;
        mid->next=phead;
        phead=mid;
        mid=next;
    }
    return phead;//返回反转链表的头结点
}

bool isPalindrome(struct ListNode* head)
{
    struct ListNode*mid=midhead(head);
    struct ListNode*cur=reverselink(mid);
    while(cur)
    {
        if(cur->val!=head->val)//只要有不相等的结点，直接返回false
        {
            return false;
        }
        else
        {
           //依次遍历两个链表，一个反转的和一个没反转的
           cur=cur->next;
           head=head->next;
        }
    } 
    return true;
}

🍁2.把值存入数组中，然后使用双指针 

这个思路非常简单，依次把链表的值存入一个数组中，然后使用left指针和right指针把数组遍历完即可。这是一种取巧的思路，这题要的就是第一种解法的思路，如果面试会考这个题，这种数组的方式肯定是不行的。但是我们是练题，肯定要多种方法都要掌握。

bool isPalindrome(struct ListNode* head)
{
   int arr[100000]={0};//注意这里是10的五次方，因为它提示链表的结点是1到10的五次方
   int i=0;
   while(head)
   {
       arr[i++]=head->val;
       head=head->next;
   }
    int left=0;
    int right=i-1;
    while(left<right)
    {
        if(arr[left]!=arr[right])
        {
           return false;
        }
        left++;
        right--;
    }
   return true;
}

🌼二.交换链表中的结点 

给你链表的头节点 head 和一个整数 k 。
交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。
示例 1：
 

输入：head = [1,2,3,4,5], k = 2
输出：[1,4,3,2,5]

示例 2：

输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5
输出：[7,9,6,6,8,7,3,0,9,5]

示例 3：

输入：head = [1], k = 1
输出：[1]

示例 4：

输入：head = [1,2], k = 1
输出：[2,1]

示例 5：

输入：head = [1,2,3], k = 2
输出：[1,2,3]

提示：

• 链表中节点的数目是 n
• 1 <= k <= n <= 105
• 0 <= Node.val <= 100

做题链接：交换链表中的结点 

🍂1.快慢指针

要交换正数第k个结点和倒数第k个结点的值，就必须要找到这个两个结点，这题的目的就是如何找到这两个结点。
正数第k个结点还是很好找的，直接从头开始遍历链表，走一个结点，count就加1，当count值和k的值相等之后，即找到了正数第k个结点。那倒数第k个结点如何找呢？其实也很简单，因为正数k个结点和倒数第k个结点时对称的，所以这是我们只需要再定义一个指针(快指针)，从头开始走，另一个指针就从刚刚找到的正数第k个指针(慢指针)开始走，它们两个指针同时走，直到慢指针走到尾，这时快指针所指向的位置就是倒数的k个位置。

struct ListNode* swapNodes(struct ListNode* head, int k)
{
    if(head==NULL&&head->next==NULL)
        return head;
    struct ListNode*fast=head,*slow=head;
       int count=0;
       while(fast)//该循环找正数第k个结点
       {
          count++;
          if(count==k)
            break;
            fast=fast->next;
       }
       struct ListNode*cur=fast;
        while(fast->next)//找倒数第k个结点
        {
           slow=slow->next;
           fast=fast->next;
        }
        int temp=cur->val;//定义一个遍量交换值
        cur->val=slow->val;
        slow->val=temp;
        return head;
}