题解 | #反转链表#

思路1
三个指针，一个指向pre，一个指向cur，一个指向next。对每一个节点，调整其next指针指向前一个节点。

public class Solution {
  public ListNode ReverseList(ListNode head) {
      ListNode preNode = null,curNode = null,nextNode = null;
      curNode = head;

      while(curNode!=null){
          nextNode = curNode.next;
          //翻转
          curNode.next = preNode;
          preNode = curNode;
          curNode = nextNode;
      }
      return preNode;
  }

思路2
利用栈先进后出的特性，重新建立链表

import java.util.Stack;
public class Solution {
  public ListNode ReverseList(ListNode head) {
      Stack<ListNode> stack=new Stack();
      while(head!=null){
          stack.push(head);
          head = head.next;
      }
      if(stack.empty()) return null;
      ListNode resHead = stack.pop();

      ListNode ptr = resHead;
      while(!stack.empty()){
          ptr.next = stack.pop();
          ptr = ptr.next;
      }
      ptr.next = null;
      return resHead;
  }
}

思路3
利用递归，将递归函数的next连接到当前节点

public class Solution {
  ListNode newHead = null;
  public ListNode ReverseList(ListNode head) {
      if(head ==null||head.next == null) {
          newHead = head;
          return head;
      }
      ListNode curNode = ReverseList(head.next);
      (head.next).next = head;
      head.next = null;
      return curNode;
  }
}