单链表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。

我们继续深入解析以下结束的循环条件是如何得到的，这就得要根据节点个数是否为奇数和偶数来确定。 

1）当讨论的节点个数为偶数的时候: 

阶段1：

阶段2： 

阶段3：

 从这里可以得到，当我们得fast指针指向NULL时，循环结束，此时，slow指向得节点正好是我们需要得中间节点。

2）当讨论的节点个数为奇数的时候: 

阶段1：

阶段2：

阶段3：

从这里，我们可以看出来，当fast的next指向为NULL时，我们的循环结束，此时，slow指针指向的节点就是我们的中间节点。

然后，我们得出结论，当fast和fast->next有一个为NULL时，我们的循环条件就结束，此时我们的slow指针指向的节点就是中间节点。 （这里的）

快慢指针法总结：

这里的快慢指针法可以很快的找到我们所需要的单链表中的中间节点，代码量也很少，是一个很不错的解题思路，在涉及到用中间节点解题的时候，可以参考以下这个方法。