力扣206-反转链表（Java，迭代）

 

 迭代法：

先拿简单的举例子，1->2->null

链表只能从头开始遍历，先在纸上手写：

第一步，1.next=null

第二步，2.next=1

第三步，返回2

这是总体的步骤。

——————————————

下面思考实现：

第一步很好实现，但是看第二步发现需要知道1原来的next才行，所以加一个rest=1.next，放在第一步之前，所以现在是：

第0步，rest=1.next

第一步，1.next=null

第二步，2.next=1

第三步，返回2

——————————————

从特殊到一般，如果要总结出一般规律，上面的实例都要被替换。可以看出来1是目前正在处理的节点，放到一般情况就用cur这个节点来代替，如果cur不是首位，那么指向的应该是cur的前一个节点，用pre来代替。并且在实际移动中cur肯定是要从头往后移动的，所以思路成了：

第0步，rest=cur.next ，pre=null         //保留后面的地址，

第一步，cur.next=pre          //当前节点指向其前一个

第二步，pre=cur         //pre变成cur，前移一个

循环：cur=cur.next           //当cur不为空的时候，后移遍历链表

第三步，返回pre（这个返回是拿实例做看出来的）

好了，现在就可以写出代码了！

/**
 * Definition for singly-linked list.
 * public 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 reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode cur=head,pre=null;
        while(cur!=null)
        {
            ListNode rest=cur.next;
            cur.next=pre;
            pre=cur;
            cur=rest;
        }
        return pre;
    }
}

递归法我推荐看题解第二页这篇：