原题链接：https://leetcode.cn/problems/reverse-linked-list

本题有两种解法。

双指针

其本质就是将当前节点的下一个节点由之前的next改为pre，这样就能完成当前节点的反转， 如此一直往后遍历链表， 并不断重复这个过程。由于在反转的过程中会造成链表的断开， 所以需要一个临时变量来保存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode reverseList(ListNode head) {
     // 当前节点的上一个节点， 初始化的时候头结点的上一个节点不存在，所以为null
     ListNode pre = null;
     // 当前节点
     ListNode cur = head;
   
     // 当遍历到最后一个节点的时候，cur指向了null，此时遍历结束
     while (cur != null){
         // 临时保存一下当前节点的next节点
         ListNode tmp = cur.next;
         // 先将当前节点的next指向前一个节点， 这样就完成了当前节点的反转
         cur.next = pre;

         // 完成反转之后，再将pre和cur都向后移动一位（使遍历能继续进行下去）
         pre = cur;
         cur = tmp;    
     }
     // 在最后一次完成反转之后， 结合图形我们可以看到，pre指向的就是新链表的头节点
     return pre;
 }

递归

其思路和双指针类似， 只不过继续进行遍历的方式不同， 双指针使用的是移动指针，递归使用的是自身函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ListNode reverseList1(ListNode head) {
        // 和双指针的思路一样，初始化的时候pre是null, cur是head
        return reverse(null, head);
    }

    /**
     * 将pre和cur进行反转，返回反转之后的头结点
     * @param pre
     * @param cur
     * @return
     */
    public ListNode reverse(ListNode pre, ListNode cur){
        // 递归的终止条件和双指针一样，都是当cur为null时退出， 此时头结点指向的是pre
        if (cur == null){
            return pre;
        }
        ListNode tmp = cur.next;
        // 反转pre和cur
        cur.next = pre;

        // 反转完成之后，就需要继续反转下一个节点
        return reverse(cur, tmp);
    }