单链表OJ题（2）：反转链表、找中间节点

1.反转链表

反转链表总结：

2.链表的中间节点（快慢指针法）

快慢指针法总结

1.反转链表

在这道题中，我们需要把一个单链表反转它们的指向，这里，我们给出了一个好理解的简单解法，就是用三个指针去解决这道题。先给出完整的代码。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    //创建头指针
    ListNode* n1 = NULL;
    ListNode* n2 = head;
    if(n2==NULL){
        return NULL;
    }
    ListNode* n3 = n2->next;
    while(n2){
        n2->next=n1;
        n1 = n2;
        n2 = n3;
        if(n3)
            n3=n3->next;
    }
    return n1;
}

假设，我们的原链表为head，我们申请了n1，n2，n3三个指针，其中，n1初始化为NULL，n2初始化为head（图中的第一个节点），n3初始化为head->next（也就是图中的第二个节点）

第一次操作：

第二次操作：

第三次操作：

第四次操作：（注意：最后一次操作，n3的指针指向，不能让n3出现NULL->NULL的情况）

然后，我们的步骤如下：

1、遍历原链表中的每个节点，每次遍历，先使n1的指针指向n2的节点（n1=n2），然后让n2的节点指向n3（n2=n3），最后让n3的节点指向n3的下一个节点（n3=n3->next）

2、注意，要在循环中判断以下n3的指针指向，防止出现NULL->NULL的情况。

反转链表总结：

这里面最重要的是我们要改变当前的节点的指向关系的时候，注意要先把当前节点指向的下一个节点的指针保存下来。如果我们不保存就改变指向关系的化，就会导致一个严重的错误，我们原链表中当前节点的下一个节点就找不到了。如下图，当我们遍历原链表的时候，我们需要让第一个链表的节点指向NULL，但是我们没有存储第二个节点的地址，当我们改变了指向让第一个节点的地址为NULL的时候，原链表后面的节点就没办法找到。

这个时候，我们就需要在改变当前节点指向关系前将这个节点的next域存储起来，这样我们就可以实现通过n3找到原链表节点，通过n2就可以改变当前链表的指向关系。

2.链表的中间节点（快慢指针法）

（1）在看到这个题的时候，我们能够都想到的同用解法是用计数器来做 ，下面是具体步骤:

1、首先我们遍历原链表，定义一个变量count存储节点的个数，然后将每个节点都做+1的操作，这样我们就得到了链表的节点总个数count。

2、然后，我们对count/2得到中间节点的位置，然后再次遍历原链表，找到下标为：count/2的位置上的节点，并返回。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    ListNode* pcur = head;
    int count = 0;
    while(pcur){
        count++;
        pcur = pcur->next;
    }
    pcur = head;
    count /= 2;
    while(count--){
        pcur = pcur->next;
    }
    return pcur;
}

（2）这里提供一种很巧妙的解题方法，我们只需要遍历一遍链表就能够得到链表中间的位置，这个就是我们接下来介绍的快慢指针法了。

先给出代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    if(head==NULL){
        return NULL;
    }
    //定义快慢指针
    ListNode* slow ,*fast;    
    slow = fast = head;
    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

1、刚开始，我们创建两个指针，slow和fast都指向头节点.

2、接下来，我们规定，slow每次走一个节点，fast每次走两个节点，当遍历结束时，slow指针指向的节点就是我们需要的中间节点。

3、循环结束的条件，fast!==NULL && fast->next!=NULL。