1. 迭代方法

1.1. 代码实现

1
2
3
4
5
6
7
8
9
10
11
public static ListNode iterate(ListNode head) {  
    ListNode prev = null, curr, next;  
    curr = head;  
    while (curr != null) {  
        next = curr.next;  
        curr.next = prev;  
        prev = curr;  
        curr = next;  
    }  
    return prev;  
}

1.2. 理解要点

1.2.1. 初始化变量

1.2.2. 移动指针

处理下一个节点：
prev移动到curr位置：prev = curr
curr移动到下一个节点位置：curr = next
然后继续，暂存指针next = curr.next，改变指针curr.next = prev

2. 递归方法

2.1. 代码实现

1
2
3
4
5
6
7
8
9
public static ListNode recursion(ListNode head) {  
    if (head == null || head.next == null) {  
        return head;  
    }  
    ListNode newHead = recursion(head.next);  
    head.next.next = head;  
    head.next = null;  
    return newHead;  
}

2.2. 理解要点

  1. newHead只是为了得到反转后的头节点。当递归第⑤次，来到最后一个节点时，return到该节点并赋值给newHead，后面递归出栈后不再参与计算。

  1. 在递归开始归的时候，被调用方法⑤出栈后，回到调用方执行点入口，当时recursion的参数（head.next）中的head为节点4，在执行了head.next.next = head后，节点5的next指向了节点4；在执行了head.next = null后，节点4的next指向了null

走完37、38行，就把节点4反转成功了，如下图所示。依次类推，一直倒到递归入口处，返回反转后的newHead，即节点5

2.3. 单个节点反转

示意图

3. 参考

3.1. 抖码课堂

https://www.bilibili.com/video/BV1qL411M7iB/?p=39&spm_id_from=pageDriver&vd_source=c5b2d0d7bc377c0c35dbc251d95cf204

3.2. 吴师兄学算法

https://blog.algomooc.com/024.html#%E4%BA%8C%E3%80%81%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90