/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
 /**
  *
  * @param pHead ListNode类
  * @return ListNode类
  */
//方法一：迭代法
struct ListNode* ReverseList(struct ListNode* pHead)
{
  if (!pHead)   //如果链表为空，则不需要进行翻转，直接返回原结点
    return pHead;
  struct ListNode* n1, * n2, * n3;    //定义三个指针，n1，n2用来进行翻转，n3用来记录下一个位置
  n1 = NULL;
  n2 = pHead;
  n3 = pHead->next;
  while (1)
  {
    n2->next = n1;  //将后面结点的指针域指向前面的结点，实现翻转
    n1 = n2;  //指针下滑
    n2 = n3;  //指针下滑
    if (!n2)    //当n2为空的时候，结束循环，此时n1为新链表的头结点
      break;
    n3 = n3->next;  //指针下滑
  }
  return n1;
}

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
 /**
  *
  * @param pHead ListNode类
  * @return ListNode类
  */
//方法二：创建新链表，将旧链表的结点从前往后头插到新链表，实现旧链表的翻转
struct ListNode* ReverseList(struct ListNode* pHead)
{
  struct ListNode* newHead = NULL;  //创建新链表的头结点
  struct ListNode* cur = pHead, *end = pHead->next; //定义两个指针用来记录当前位置和保存下一个位置
  while (cur)   //若当前位置为空，则直接退出循环
  {
    cur->next = newHead;  //使当前位置的指针域指向新的头
    newHead = cur;    //更改头结点位置
    cur = end;  //记录当前位置的指针下滑
    if (!cur) //如果cur下滑后为空，则立即退出循环，防止end变为野指针
      break;
    end = end->next;  //end下滑
  }
  return newHead; //返回新的头
}