侧边栏壁纸
博主头像
buukle博主等级

布壳儿

  • 累计撰写 106 篇文章
  • 累计创建 15 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

administrator
2021-06-22 / 0 评论 / 0 点赞 / 182 阅读 / 1324 字

题目 : 给你单链表的头指针 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

评论区