链表反转

这是一个简单明了的反转

struct ListNode {
  int value;
  ListNode* next;
}

//迭代反转
ListNode* reverse(ListNode* head){
//初始化
ListNode* pre = NULL; // 存储前一结点
ListNode* cur = head; //存储当前结点
ListNode* next = NULL; //存储后面结点

while(cur){
  next = cur -> next; //先存后面结点，防止掉链子，预备反转
  cur -> next = pre; //链表反转
  pre = cur;
  cur = next;  //pre和cur 移动
}

return pre; //返回最新的头
}

//递归反转
ListNode* recursionRevserse(ListNode* head){
//确定边界，递归底部
if(head == NULL || head -> next == NULL) 
  return head;

ListNode* reversedListHead = recursionReverse(head -> next); //一直追问邻居，给我返回一个反转的链表，不包括我自己（递归向下）
head -> next -> next = head; //将我自己加入这个反转的链表
head -> next = NULL;  //将我自己与隔壁老王的正向关系断开
return reversedListHead; //这是一直往上送的表头（递归向上）


}