描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

要求：空间复杂度 O(1)，时间复杂度 O(n)。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}

通过对题目的分析，要求空间复杂度为O(1)，就不能使用额外的空间，例如使用List等结构，时间负载度为O(n)，也就是只能使用单重for循环

对于单链表来说，我们只能找到一个节点的next，因此，如果需要将next指向上一个节点，就必须记录上一个节点，因此，我们可以使用双指针的方式来翻转链表。我们通过图来看一下链表翻转的步骤

流程图

算法实现

下面，我们来看一下代码实现

public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}


public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null) {
            return null;
        }
        
        ListNode prev = head;
        ListNode current = prev.next;
        // 必须断开，否则会形成环
        prev.next = null;
        while(current != null) {
            // 记录下一个节点
            ListNode next = current.next;
            // 翻转链表，将链表的下一个节点指向上一个节点
            current.next = prev;
            // 移动指针
            prev = current;
            current = next;
        }
        // 此时current == null；prev指向原链表的最后一个节点，通过翻转后，变成head
        return prev;
    }
}

算法需要练习才能掌握精髓，附上算法练习地址，有需要的小伙伴可以上去练习一下

反转链表_牛客题霸_牛客网

注：牛客网上的算法题按照专题分类，更适合突击训练使用