LeetCode 206 反转链表,LeetCode 92反转链表Ⅱ

206. 反转链表

给你单链表的头节点 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
写法一：不使用头节点，可以看到需要三个变量

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

写法二：使用头节点，你可以发现用了四个变量，因为你需要使用dummy.next来返回

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy, cur = pre.next;
        while (cur != null && cur.next != null) {
            ListNode next = cur.next;
            cur.next = cur.next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummy.next;
    }
}

写法三：使用递归的方法，最简洁，但需要思考

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode re = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return re;
    }
}

92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

写法一：使用头节点，可以看出来很简单

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode pre = new ListNode(0, head);
        ListNode dummy = pre;
        int cnt = right - left;
        while (left-- > 1) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        for (int i = 0; i < cnt; i++) {
            ListNode next = cur.next;
            cur.next = cur.next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummy.next;
    }
}

写法二：对反转链表的不使用头节点有很深的理解，我最开始就是用的这种

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode start = head, end = head;
        ListNode prefix = new ListNode(0, head);
        int temp = left;
        while (left-- > 1) {
            prefix = prefix.next;
            start = start.next;
        }
        while (right-- > 1) {
            end = end.next;
        }
        ListNode last = end.next;
        ListNode pre = last;
        while (start != last) {
            ListNode next = start.next;
            start.next = pre;
            pre = start;
            start = next;
        }
        if (temp == 1) return pre;
        prefix.next = pre;
        return head;
    }
}