【leetcode206 反转链表】

反转一个链表

示例：
输入:1->2->3->4->5->NULL
输出:5->4->3->2->1->NULL

迭代

使用一个变量 pre 记录前驱节点,使用一个变量 next 记录后继节点，不断更新 current.next = pre 就好了，不过尤其要注意的问题是：

• 头尾指针点的处理
• 指针循环引用导致的死循环 ```c /**
  • Definition for singly-linked list.
  • struct ListNode {
  • int val;
  • struct ListNode *next;
  • }; */

struct ListNode reverseList(struct ListNode head){ struct ListNode currentNode = head; struct ListNode preNode = NULL; while (currentNode) { struct ListNode *next = currentNode->next; currentNode->next = preNode; preNode = currentNode; currentNode = next; } return preNode; }

<a name="9FKxz"></a>
### 递归
链表具有天然的递归属性，比如我们要反转 `1->2->3->4->5->NULL` 那么其实可以将其拆解为 反转 `1`  和  `2->3->4->5->NULL` ,依次类推，知道最后是反转 `5->NULL` ,当达到尾节点的时候，直接返回 `5`  所以这个时候就是递归的终结条件，这是 `递` 的过程，接下来我们看看如何 `归` ，尾结点已经说了，直接返回 `5` 即可，当返回到上一层的时候 `head` 指向 `4` 这个时候其实我们是希望 `4` 和 `5` 来个反转，那么也就是 `5` 指向 `4` 但是这个时候 `head` 指向的是 `4`  也就是 `head->4->5` 那么只要 `head->next->next = head` 就实现了反转，但是这个时候有个问题，链表形成了环，所以我们要把 `4->5` 此处打断： `head->next = NULL` 即可。
```c
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head){
    if (head == NULL || head->next == NULL) return head;
    struct ListNode *node = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return node;
}