92. Reverse Linked List II 「反转链表 II」

2020年04月03日 91点热度 0人点赞 0条评论

将链表从 m 到 n 的元素进行反转。要求只扫描一次链表。

提示: 1 ≤ m ≤ n ≤ 链表长度

举例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

此题思路与 反转链表 相似,不过多了两步考虑,即需要记录反转节点前的一个节点,与最后反转节点后的一个节点,在中间部分完成反转后依次连接即可。

此题使用了一个伪头部节点来辅助思考,方便考虑边界情况。如果不使用,需要在最后部分多写几个判断代码来确定应该返回的节点。

/*
 * 92. Reverse Linked List II
 * https://leetcode.com/problems/reverse-linked-list-ii/
 * https://realneo.me/92-reverse-linked-list-ii/
 */

public class ReverseBetween {
    public static void main(String[] args) {
        ReverseBetween solution = new ReverseBetween();

        ListNode head = new ListNode(1);
        ListNode node = head;
        for (int i = 2; i < 4; i++) {
            node.next = new ListNode(i);
            node = node.next;
        }

        solution.print(head);
        head = solution.reverseBetween(head, 2, 3);
        solution.print(head);
    }

    private void print(ListNode node) {
        for (; node != null; node = node.next) {
            System.out.print(node.val);
            System.out.print("->");
        }
        System.out.println("null");
    }

    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode con = dummyHead, tail = head;
        int i = 1;

        while (i < m) {
            con = tail;
            tail = tail.next;
            i++;
        }

        ListNode prev = null, node = tail;

        while (i <= n) {
            ListNode next = node.next;
            node.next = prev;
            prev = node;
            node = next;
            i++;
        }

        con.next = prev;
        tail.next = node;

        return dummyHead.next;
    }
}

Neo

与卿再世相逢日,玉树临风一少年。

文章评论