1. 首页
  2. Leetcode经典148题

leetCode-92-Reverse-Linked-ListII

题目描述(中等难度)

leetCode-92-Reverse-Linked-ListII

给定链表的一个范围,将这个范围内的链表倒置。

解法一

首先找到 m 的位置,记录两端的节点 left1 和 left2 。

然后每遍历一个节点,就倒置一个节点。

到 n 的位置后,利用之前的 left1 和 left2 完成连接。

为了完成链表的倒置需要两个指针 pre 和 head。为了少考虑边界条件,例如 m = 1 的倒置。加一个哨兵节点 dummy。

m = 2, n = 4

1 2 3 4 5 加入哨兵节点 d,pre 简写 p,head 简写 h

0 1 2 3 4 5 往后遍历
^ ^
d h
p

0 1 2 3 4 5 此时 h 指向 m 的位置,记录 p 和 h 为 l1 和 l2
^ ^ ^
d p h

0  1  2 3 4 5 然后继续遍历
^  ^  ^
d  p  h
  l1  l2

0  1  2  3 4 5 开始倒置链表,使得 h 指向 p
^  ^  ^  ^
d  l1 p  h
     l2

当前状态用图形描述

leetCode-92-Reverse-Linked-ListII

倒转链表,将 h 的 next 指向 p,并且后移 p 和 h。

leetCode-92-Reverse-Linked-ListII

然后上边一步会重复多次,直到 h 到达 n 的位置。当然这道题比较特殊,上图 h 已经到达了 n 的位置。

此时,我们需要将 h 指向 p,同时将 l1 指向 h,l2 指向 h.next,使得链表接起来。

leetCode-92-Reverse-Linked-ListII

操作完成,将 dummy.next 返回即可。

public ListNode reverseBetween(ListNode head, int m, int n) {
    if (m == n) {
        return head;
    }
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    int count = 0;
    ListNode left1 = null;
    ListNode left2 = null;
    ListNode pre = dummy;
    while (head != null) {
        count++;
        //到达 m,保存 l1 和 l2
        if (count == m) {
            left1 = pre;
            left2 = head;
        }
        // m 和 n 之间,倒转链表
        if (count > m && count < n) {
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
            continue;
        }
        //到达 n
        if (count == n) {
            left2.next = head.next;
            head.next = pre;
            left1.next = head;
            break;
        }
        //两个指针后移
        head = head.next;
        pre = pre.next;
    }
    return dummy.next;
}

时间复杂度:O(n)。

空间复杂度:O(1)。

考察链表知识,如果对链表很熟悉,在纸上画一画,理清楚怎么指向,很快可以写出来。

作者:windliang

来源:https://windliang.cc

JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:leetCode-92-Reverse-Linked-ListII

链接:https://www.javajike.com/article/3228.html

« leetcode-91-Decode-Ways
leetCode-93-Restore-IP-Addresses»

相关推荐

QR code