注意，先明确词语——“指向”的意义。“X节点的下一节点为Y” 与 “X节点指向Y”同义。

非递归反转

• 思路：遍历链表，在遍历的同时修改链表的方向：
  • 通过传入一个链表头head进行循环遍历。链表结构如下：

• 为了使代码更有可读性，我们可以定义一个变量curr代表当前遍历的节点。初始化时自然为链表的第一个节点，即head节点。
• 反转的思路非常简单，当遍历到第一个节点curr时，我们只需让当前节点指向前一个节点即可，但此时没有前一个节点的概念，所以我们需要定义一个pre_Node变量，并初始化为null。

• 但如果单纯进行了上述改变，会发现node1节点失去了引用变量，导致我们无法找到它，也就意味着无法继续遍历后面的节点，因此，我们需要在遍历的过程中，第一时间将node1节点（即curr.next节点）保存起来赋予一个变量temp。

• 然后再将curr指向前一个节点pre_Node

• 现在，第一个节点curr已经转换完毕，接下来就要思考如何改变前一节点pre_Node和当前节点curr然后继续往下遍历。
  • pre_Node：
    • 在上面的操作完成以后，相对于当前节点的前一节点pre_Node已经被赋值给了curr.next，这意味着它在本次遍历中已经失去了价值，所以我们需要让pre_Node接着往后指向当前节点。
  • curr：
    • 既然前一节点pre_Node此时已经指向了当前节点curr，那么当前节点curr自然也要往下指向下一节点。
    • 而在第一时间，我们已经通过temp变量把节点node1的引用储存了起来，所以现在只需要让 curr = temp即可。

• 参照上述针对curr节点的操作，可以发现在这一过程中，真正表示当前节点的变量是pre_Node，这也就意味着pre_Node在最后将指向链表反转后的新链表的头节点。所以在遍历结束以后，我们只需返回pre_Node变量即可。

  public Node Reverse(Node head)
  {
  var curr = head;            //当前节点
  Node pre_Node = null;        //前一节点
  while(curr != null)            //遍历到当前节点为null时结束
  {
     var temp = curr.next;    //储存后一节点
     curr.next = pre_Node;    //当前节点指向前一节点
     pre_Node = curr;        /*前一节点向后跳。即指向当前节点，作为下次的前一节点，
                               以备下次遍历*/
     curr = temp;            /*当前节点向后跳。即指向下一节点，作为下次的当前节点，
                               以备下次遍历*/
  }
  return pre_Node;            //返回前一节点代表的当前节点，即反转后新链表的头节点
  }

  递归反转

• 思路：
  • （1）通过递归找到最后一个节点，然后层层返回。返回以后的这个节点将成为反转后链表的头节点head。
  • （2）在递归的过程中对当前节点（除最后节点）的左右指向进行反转。
• 首先实现（1）：
  • 由于我们需要找到最后一个节点，所以这也就意味着，当当前节点的下一节点为空时，该节点即为最后一个节点，此时，我们需要返回当前节点。
  • 另外，我们还需要做一个非空判断，若当前传入的链表为空，即头节点为空，此时也应当返回当前节点。
  • 递归查找最后一个节点需要满足如下递归函数：

f(x) = f(x.next)
即：
Reverse(curr) = Reverse(curr.next)
用代码表示如下：

public Node Reverse(Node curr)
{
    if (curr == null || curr.next == null) return curr;
    return Reverse(curr.next);
}

• 然后实现（2）：
  • 我们需要让当前节点的下一节点指向当前节点，当前节点再指向Null，如此完成针对当前节点的左右指向反转。

curr.next.next = curr;
curr.next = null;

• 这一过程我们需要在找到最后一个节点之后操作，原因是如果在找最后一个节点之前实现了节点的左右反转，就会改变原有指向，从而无法找到最后一个节点。因此，我们需要在递归函数执行之后，返回值返回之前实现该过程。
• 过程介于递归函数的执行与返回之间，所以我们应当把return Reverse(curr.next)用变量p分开，可表示为： ```csharp var p = Reverse(curr.next);

//过程 curr.next.next = curr; curr.next = null; //- End -

return p;

   - 完整代码如下：
```csharp
public Node Reverse(Node curr)
{
    if (curr == null || curr.next == null) return curr;
    var p = Reverse(curr.next);
    //过程
    curr.next.next = curr;
    curr.next = null;
    //- End -
    return p;
}