翻转链表

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if not pHead or not pHead.next:
            return pHead
        else:
            newHead = self.ReverseList(pHead.next)
            pHead.next.next=pHead
            pHead.next=None
            return newHead

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
  var pre *ListNode = nil
  for head!=nil {
    //先存下一个节点，不然一会就没了
    next := head.Next
    //当前节点指向上一个节点
    head.Next = pre
    pre = head
    head = next
    //等价于 pre, head, head.Next = head, head.Next, pre
  }
  return pre
}
递归：

func reverseList(head *ListNode) *ListNode {
  return reverse(nil, head)
}
​
func reverse(pre,cur *ListNode) *ListNode {
  if cur == nil {
    return pre
  }
  head := reverse(cur, cur.Next)
  cur.Next = pre
  return head
}