目录

1.链表的中间结点

2.链表中倒数第k个结点

3.反转链表

方法一：头插

方法二：倒向

 4.链表的回文结构

1.链表的中间结点

题目:给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

链接：力扣​​​​

用快慢指针。slow一次走一步，fast一次走两步。fast的步数是slow的两倍。当fast走完链表的时候，slow刚好在中间结点。

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* slow=head;
    struct ListNode* fast=head;
    while( fast && fast->next )//奇数：当fast->next==NULL跳出 偶数：当fast==NULL跳出
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

---

2.链表中倒数第k个结点

题目：输入一个链表，输出该链表中倒数第k个结点。

链接：链表中倒数第k个结点_牛客题霸_牛客网

要倒数第k个结点地址。fast先走k步，和slow有了一个距离。两个指针再同时走，一次一步。两个指针的距离不变，当fast走到空，slow就是我们想要的结点。

举个例子：fast先走一步，slow和fast再同时走。fast走到空，slow在fast的前一个结点。就是倒数第一个结点。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* fast=pListHead;
    struct ListNode* slow=pListHead;
    while(k--)//fast先走k步
    {
        if(fast==NULL)//fast还没走够k步就等于空了，说明k大于链表长度
        {
            return NULL;
        }
        fast=fast->next;
    }

    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

---

3.反转链表

题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

链接：力扣​​​​​

方法一：头插

不停头插，就倒置了。

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* newhead=NULL;
    struct ListNode* cur=head;
    struct ListNode* next=NULL;
    while(cur)
    {
        next=cur->next;
        cur->next=newhead;//更改了cur的next，找不到cur的下一个了，所以要提前保存cur的next
        newhead=cur;
        cur=next;
    }
    return newhead;

}

方法二：倒向

truct ListNode* reverseList(struct ListNode* head){
    if(head==NULL)//链表为空的情况
    {
        return NULL;
    }
    
    struct ListNode*n1,*n2,*n3;
    n1=NULL;
    n2=head;
    n3=n2->next;
    while(n2)
    {
        //倒向
        n2->next=n1;
        
        //迭代
        n1=n2;
        n2=n3;
        if(n3!=NULL)//防止越界访问 n3先走到空，下一次循环n2走到空我们才完整的转换了链表的指向。n3依旧为空，如果还继续迭代成n3的next就是越界访问。
        {
            n3=n3->next;
        }

    }
    return n1;

}

---

 4.链表的回文结构

题目：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

链接：链表的回文结构_牛客题霸_牛客网

思路：找到中间结点，逆置后半段。两个指针一个直指向原链表头，一个指向后半段逆置后的新头结点。同时开始遍历链表。

class PalindromeList {
public:

    //找中间结点
    struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* slow=head;
    struct ListNode* fast=head;
    while( fast && fast->next )//奇数：当fast->next==NULL跳出 偶数：当fast==NULL跳出
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}
    
    //逆置链表
    struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* newhead=NULL;
    struct ListNode* cur=head;
    struct ListNode* next=NULL;
    while(cur)//头插
    {
        next=cur->next;
        cur->next=newhead;
        newhead=cur;
        cur=next;
    }
    return newhead;
}
    bool chkPalindrome(ListNode* A) {
        struct ListNode* head=A;//没啥特别意义，就是规范一下命名
        struct ListNode* mid=middleNode(head);
        struct ListNode* rHead =reverseList(mid);
        
        //因为倒置，mid到了rhead的尾，mid的next为空。从head和rhead开始同时遍历链表，当访问到mid前的一个结点，该节点的next依旧指向mid，链表相交。偶数个结点，rhead提前走到空，奇数个同时走到空。
        
        while(rHead)
        {
            if(head->val == rHead->val)//相等继续往后走
            {
                head=head->next;
                rHead=rHead->next;
            }
            else//有一个不相等就不是回文结构
            {
                return false;
            }
        }
        
        return true;
        
    }
};