leetcode.206.反转链表

题目

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

思路

• 双指针:创建指针p,curr，初始分别指向null和头节点，每轮循环移动一个节点的指向，直到指到最后一个位置为止。
  
• 递归法:基于双指针。注意递归的退出条件

实现

• 双指针

class Solution {
    public ListNode reverseList(ListNode head) {
             
        ListNode p = null;
        ListNode curr = head;

    //注意这里退出循环得条件，因为curr是在指针翻转之后才赋
    //值，所以最后当curr为null得时候其实已经全部翻转完成了
        while(curr != null){
            ListNode temp = curr.next;
            curr.next = p;

            p = curr;
            curr = temp;
        }
    return p;  
    }
}

• 递归法

class Solution {
    public ListNode reverseList(ListNode head) {
            
      ListNode pre = null;
      ListNode curr = head;      
      return  reverse(pre,curr);
         
    }

    public ListNode reverse(ListNode pre,ListNode curr){
          
          //递归退出条件
          if(curr == null) {
              return pre;
          } else{
             ListNode temp = curr.next;
             curr.next = pre;
             //注意这里也需要return的
             return  reverse(curr,temp); 
          }
          
        
    }
}