[每日一题]翻转链表

public class ListNode {

 private int val;
 private ListNode next;

}

/**
 * 递归实现
 */
 /**
  * 递归实现,将前置节点作为参数传递,初始调用pre=null
  */
 private static ListNode reverse2(ListNode head, ListNode pre) {
   // write your code here
   //如果当前节点为空,返回前置节点,这样可以再结束时拿到头结点
   if (head == null) {
     return pre;
   }
   //保存后继节点
   ListNode next = head.next;
   //将当前节点的next指针指向前置节点(翻转操作)
   head.next = pre;
   //翻转下一个节点及其前置节点
   return reverse2(next, head);
 }

/**
 * 非递归实现,直接传入当前节点即可
 */
public static ListNode reverse(ListNode head) {
  // write your code here
  //初始化将前置及后继节点置为null
  ListNode nextNode = null;
  ListNode preNode = null;

  //当前节点不为空
  while (head != null) {
    //记录后继节点
    nextNode = head.next;
    //翻转,将当前节点的next指针指向前置节点
    head.next = preNode;
    //记录当前节点(即下一次循环时的前置节点)
    preNode = head;
    //向后遍历
    head = nextNode;
  }
  //为空时返回前置节点
  return preNode;
}