反转链表

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

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

下面介绍两种思路，均能解决问题

1.改变节点指向

定义三个节点(==思考为什么定义三个而不是两个？==)而后通过指针遍历把cur指向的节点方向指向前一个，然后通过迭代到末尾，当cur为空退出循环

==代码实现如下==

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* reverseList(struct ListNode* head)
{
   
   
    if(head==NULL)
        return NULL;

    struct ListNode* prev=NULL;
    struct ListNode* cur=head;
    struct ListNode* next=head->next;

    while(cur)
    {
   
   
        cur->next=prev;

        prev=cur;
        cur=next;
        if(next)
            next=next->next;
    }

    return prev;
}

2.将每一个节点都头插

是一个新方法，只需要把新创建一个头，然后把每一个节点都头插进来即可，下面为原理图

==代码实现如下==

struct ListNode* reverseList(struct ListNode* head)
{
   
   
    struct ListNode* cur = head;
    struct ListNode* rhead = NULL;

    while (cur)
    {
   
   
        struct ListNode* next = cur->next;

        //头插
        cur->next = rhead;
        rhead = cur;

        //迭代
        cur = next;
    }
    return rhead;
}

关于代码简洁性：

代码简洁程度取决于特殊情况的处理，例如，假设这里把next定义在while循环外，那么假设参数为NULL，就需要对特殊情况做处理，此时代码就多了if条件，整体来说简洁程度就降低了

简洁程度需要对特殊情况的处理足够好，才能足够精炼解决问题

链表的中间节点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

1.遍历链表求长度

==代码实现如下==

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* middleNode(struct ListNode* head)
{
   
   
    struct ListNode* plist=head;
    int flag=0;
    while(plist)
    {
   
   
        while(plist->next!=NULL)
        {
   
   
            plist=plist->next;
            flag++;
        }
        break;
    }
    flag+=1;
    flag=flag/2+1;
    for(int i=1;i<flag;i++)
    {
   
   
        head=head->next;
    }
    return head;
}

2.快慢指针法

定义两个指针，一个指针是慢指针，每次走一步；一个指针是快指针，每次走两步。当快指针走到末尾时，慢指针走的位置恰好为整个链表的一半

相比起思路1来说，时间复杂度只是O(N)，从时间复杂度来讲，这个方法更优

具体实现原理如下图所示

==代码实现如下==

struct ListNode* middleNode(struct ListNode* head)
{
   
   
    struct ListNode* slow=head;
    struct ListNode* fast=head;
    while(fast!=NULL && fast->next!=NULL)
    {
   
   
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

链表中倒数第K个节点

描述
输入一个链表，输出该链表中倒数第k个结点。

输入：1,{1,2,3,4,5}
输出：{5}

1.遍历求长度，根据k求结果

代码思路和上题十分类似，十分简单

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
   
   
    // write code here
    struct ListNode* cur=pListHead;
    struct ListNode* prev=pListHead;
    int flag=0;
    while(cur)
    {
   
   
        cur=cur->next;
        flag++;
    }
    if(k>flag)
    {
   
   
        return NULL;
    }
    for(int i=0;i<flag-k;i++)
    {
   
   
        prev=prev->next;
    }
    return prev;
}

2.仿照上题，快慢指针的方法解决

和上题相比，略有不同的一点是，上面的快指针每次走的是一样的，而对于这个题来说，假设K=4，那么就令快指针每次走四格，其余思路和上题类似

总结原理：这里既然要求的是倒数第k个，那么就令fast指针和slow指针之间差k个，然后两个一起走，当fast指针到末尾的时候，slow所在的位置就是fast位置减去它们一开始的距离差，也就是倒数k个的位置

整体思路是十分巧妙的，其实原理和方法1类似，都是找到最后一个元素，然后再找前面倒数的元素，但相比起来使用快慢指针的方法可以让时间复杂度缩短到最少

==代码实现如下==

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
   
   
    struct ListNode* fast=pListHead;
    struct ListNode* slow=pListHead;
    for(int i=0;i<k;i++)
    {
   
   
        if(fast)
            fast=fast->next;
        else
         return NULL;
    }
    while(fast)
    {
   
   
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

这里思考
第一次走k步和走k-1步有什么区别？