侧边栏壁纸
博主头像
惊羽博主等级

hi ,我是惊羽,前生物学逃兵,现系统工程沉迷者 . 贝壳签约工程师 , 曾被雇佣为 联拓数科 · 支付研发工程师 、京东 · 京东数科 · 研发工程师、中国移动 · 雄安产业研究院 · 业务中台技术负责人 .

  • 累计撰写 101 篇文章
  • 累计创建 14 个标签
  • 累计收到 14 条评论

算法练习(13) - 反转链表中间某段

惊羽
2021-06-22 / 0 评论 / 0 点赞 / 135 阅读 / 571 字
温馨提示:
本文为原创作品,感谢您喜欢~

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

答案

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode g  = dummyHead;
        ListNode p  = dummyHead;

        for(int i =0;i<left-1;i++){
            g = g.next;
            p = p.next;
        }
        p = p.next;

        for(int i = left;i < right;i++){
            // 将p的next缓存一下
            ListNode removed = p.next;
            // p一直在left节点上,指向next.next
            p.next = p.next.next;
            // 将缓存值头插到g.next
            removed.next = g.next;
            // 将缓存值尾插到g
            g.next = removed;
        }
        return dummyHead.next;
    }
}

思路

如图 :
微信图片_20210622022851.jpg

先将指针 p ,g 同时移动到 left前节点

再把p指针后移一位到left节点

以p节点为中间点,将p后边的节点头插到p节点和g节点之间;

0
广告 广告

评论区