题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解法

解法一 双指针 头插法

• left指针指向链表头
• right指针向后遍历链表

每次用right指向节点的值创建新节点，用头插法插入到链头，将其作为新的left。

最后将head处断开

/**
 * 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 head;
        ListNode right = head.next, left = head;
        // 双指针 头插法
        while (right != null) {
            ListNode temp = new ListNode(right.val);
            temp.next = left;
            left = temp;
            right = right.next;
        }
        head.next = null;
        return left;
    }
}

时间复杂度 O(N)

解法二 双指针 + 原地反转

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) return head;
        ListNode right = head, left = null;
        // 双指针 原地反转法
        while (right.next != null) {
            ListNode temp = right.next;
            right.next = left;
            left = right;
            right = temp;
        }
        right.next = left;
        return right;
    }
}

不需要创建新的节点插入，而是在原地反转指针，节省了空间

解法三 递归

思路和解法二一致，只是迭代改成了递归