Leetcode刷题之回文链表和交换链表中的结点
竭力履行你的义务，你应该就会知道，你到底有多大的价值。 --列夫.托尔斯泰
目录
🪴一.回文链表
给你一个单链表的头节点 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 <= 1050 <= 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;
}