反转链表

题目描述

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

示例：

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

解题思路

第一种解法，使用递归，分为两步，第一步对后续的链表进行反转，第二步将当前节点添加到已反转列表的最后，如下

反转后续节点的的操作同上，直至剩下最后一个节点，就不必反转了。

因为我们需要将当前节点挂在已反转的节点的最后，所以我们需要知道最后一个节点是什么，通过图可以观察到，已反转链表的最后一个节点是当前节点在未反转链表中的下一个节点。例如当前节点 1，已反转链表的最后一个节点 2 是其在未反转链表中的下一个节点，所以我们在反转后续节点前可以先将此节点保存下来

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

第二种方法，借助于栈，根据栈的特点，后进先出，我们依次将链表中的元素添加进栈中，最后依次从栈中弹出元素，将其添加进一个新的链表中，然后返回该链表即可得到一个反序的链表

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode dummyHead = new ListNode();
    ListNode cur = head;
    LinkedList<ListNode> list = new LinkedList<>();
    while (cur != null) {
        list.push(cur);
        cur = cur.next;
    }
    cur = dummyHead;
    while (!list.isEmpty()) {
        cur.next = list.pop();
        cur = cur.next;
    }
    cur.next = null;
    return dummyHead.next;
}

反转链表II

题目描述

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

示例：

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

解题思路

还是一样，我们还是借助栈来反转链表，我们只需要将 [left, right] 范围的添加进栈中即可，同样的我们还是构建一个新的链表，对于 left 以前的节点，直接添加到新链表中，对于 [left, right] 中的节点，添加进栈中，然后依次取出添加进新链表中，对于 right 后面的节点，也是直接添加进新链表中，然后将新链表的根节点直接返回即可

public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummyHead = new ListNode();
    // 新链表的末尾
    ListNode end = dummyHead;
    // 当前遍历节点
    ListNode cur = head;
    // left 以前的节点，直接添加进新链表
    for (int i = 1; i < left; i++) {
        end.next = cur;
        cur = cur.next;
        end = end.next;
    }
    // [left, right] 中的节点，先添加进栈中，然后依次取出添加进新链表
    LinkedList<ListNode> list = new LinkedList<>();
    // 添加进栈中
    for (int i = left; i <= right; i++) {
        list.push(cur);
        cur = cur.next;
    }
    // 从栈中取出，添加进新链表
    while (!list.isEmpty()) {
        end.next = list.pop();
        end = end.next;
    }
    // right 后面的节点全部直接添加进新链表
    end.next = cur;
    return dummyHead.next;
}