leetcode206题：反转链表（迭代或是递归）

题目描述：

反转一个单链表。

示例:

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

解题思路：

递归或迭代解决。

双指针迭代:
我们可以申请两个指针，第一个指针叫 pre，最初是指向 null 的。
第二个指针 cur 指向 head，然后不断遍历 cur。
每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。

Java实现：

  

   

    

     

    
    

     

      lass Solution {
     
    
   

    

     

    
    

     
	public ListNode reverseList(ListNode head) {
     
    
   

    

     

    
    

     
		//申请节点，pre和 cur，pre指向null
     
    
   

    

     

    
    

     
		ListNode pre = null;
     
    
   

    

     

    
    

     
		ListNode cur = head;
     
    
   

    

     

    
    

     
		ListNode tmp = null;
     
    
   

    

     

    
    

     
		while(cur!=null) {
     
    
   

    

     

    
    

     
			//记录当前节点的下一个节点
     
    
   

    

     

    
    

     

      			tmp = cur.next;
     
    
   

    

     

    
    

     
			//然后将当前节点指向pre
     
    
   

    

     

    
    

     

      			cur.next = pre;
     
    
   

    

     

    
    

     
			//pre和cur节点都前进一位
     
    
   

    

     

    
    

     

      			pre = cur;
     
    
   

    

     

    
    

     

      			cur = tmp;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		return pre;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
  
 

  
 
 

迭代实现：

递归的两个条件：

终止条件是当前节点或者下一个节点==null
在函数内部，改变节点的指向，也就是 head 的下一个节点指向 head 递归函数那句

head.next.next = head
很不好理解，其实就是 head 的下一个节点指向head。
递归函数中每次返回的 cur 其实只最后一个节点，在递归函数内部，改变的是当前节点的指向。

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
	public ListNode reverseList(ListNode head) {
     
    
   

    

     

    
    

     
		//递归终止条件是当前为空，或者下一个节点为空
     
    
   

    

     

    
    

     
		if(head==null || head.next==null) {
     
    
   

    

     

    
    

     
			return head;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		//这里的cur就是最后一个节点
     
    
   

    

     

    
    

     
		ListNode cur = reverseList(head.next);
     
    
   

    

     

    
    

     
		//这里请配合动画演示理解
     
    
   

    

     

    
    

     
		//如果链表是 1->2->3->4->5，那么此时的cur就是5
     
    
   

    

     

    
    

     
		//而head是4，head的下一个是5，下下一个是空
     
    
   

    

     

    
    

     
		//所以head.next.next 就是5->4
     
    
   

    

     

    
    

     

      		head.next.next = head;
     
    
   

    

     

    
    

     
		//防止链表循环，需要将head.next设置为空
     
    
   

    

     

    
    

     

      		head.next = null;
     
    
   

    

     

    
    

     
		//每层递归函数都返回cur，也就是最后一个节点
     
    
   

    

     

    
    

     
		return cur;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
  
 

  
 
 

文章来源: blog.csdn.net，作者：小小谢先生，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/xiewenrui1996/article/details/112969062