LeetCode206（反转链表）

题目：

　　用循环和递归的方法实现反转链表

思路：

　　由于在反转链表的过程中链表会断开，所以需要定义多指针，以记录后续节点。

代码：

1.循环方法：

  public ListNode reverseList(ListNode head) {
      if (head == null || head.next == null) {
	return head;
}
      ListNode curNode = head;
      ListNode preNode = null;
      ListNode postNode = curNode.next;
      while(curNode != null) {
      	curNode.next = preNode;
      	preNode = curNode;
      	curNode = postNode;
      	if (postNode != null) {
      		postNode = postNode.next;
	}       	
      }
      return preNode;
  }

2.递归方法：

  public ListNode reverseList1(ListNode head) {
  	if (head == null || head.next == null) {
	return head;
}
  	ListNode p = reverseList1(head.next);
      head.next.next = head;
      head.next = null;
      return p;
  }

复杂度分析及总结：

1.循环方法：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。

2.递归方法：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。由于递归栈可能会达到n。
　　总结：
　　　　递归方法较巧妙，它使反转链表从表尾开始，不需要多余指针防止链表断开。