2.反转链表

题目

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

思路

比如原链表是1->2->3->4->5->null，反转后应该是5->4->3->2->1->null。

更清楚的：

反转前：1->2->3->4->5->null
反转后：null<-1<-2<-3<-4<-5

我们注意到，节点具体的值和位置是不变的，变的只是指针和null值的位置。

那么我们可以采用双指针的解法，一个pre指针指向head的前一位，用来反转后代表null值（null<-1<-2<-3<-4<-5）。

一个cur指针从head开始往后遍历原链表，并且每遍历一个节点，指针要向前反转一次，直到遇到原链表的null值，此时pre值指向链表的最后一个节点，最后return pre即可。

但是这个过程中有个问题，我们来模拟一下。一开始，pre指针指向null值，cur指针指向head节点，cur指针的next指针指向pre后，pre向后遍历，但是cur再向后遍历时候，发现指针已经没了(为了便于区分，...代表中间什么东西也没有，也就是无next指针，此时null<-1...2->3->4->5->null)，如何再向下一个遍历？

我们可以定义个temp来临时保存cur的下一个指针即可，即temp=cur.next。这个temp是用来cur指针下一步遍历的。

  class ListNode{
    int val;
    ListNode next;
    // 别忘了写构造方法
    ListNode(){}
    ListNode(int val){
      this.val = val;
    }
    ListNode(int val,ListNode next){
      this.val = val;
      this.next = next;
    }
  }
  class Solution{
    public ListNode reverse(ListNode head){
      if(head == null){
        return null;
      }
      ListNode pre = null;
      ListNode cur = head;
      while(cur != null){
        ListNode temp = cur.next;
        // cur的next指针指向pre
        cur.next = pre;
        // pre移动到cur的位置
        pre = cur;
        // cur指针往后走一步
        cur = temp;
      }
      return pre;
  }
  }