rotateRight-旋转链表
发布日期:2021-05-18 07:53:23 浏览次数:24 分类:精选文章

本文共 1409 字,大约阅读时间需要 4 分钟。

为了将链表向右旋转k个位置,我们可以按照以下步骤进行:

  • 计算链表长度:首先,我们需要遍历链表,计算其长度n。
  • 处理特殊情况:如果k大于链表长度n,取模运算k = k % n。如果k为0,则链表不需要旋转,直接返回原链表。
  • 将链表变成循环结构:为了处理旋转,我们将链表的最后一个节点连接到链表的第一个节点,使链表形成一个循环结构。
  • 找到断点前面的节点:计算断点前面的位置pos = n - k。然后从链表的头节点开始,遍历pos次,找到断点前面的节点current。
  • 断开和重新连接:断开current与其下一个节点的连接,然后将断点后的节点连接到链表的头节点的后面,形成新的链表结构。
  • 以下是实现代码:

    class Solution {
    public ListNode rotateRight(ListNode head, int k) {
    if (head == null) {
    return head;
    }
    int n = 0;
    ListNode end = head;
    while (end != null) {
    n++;
    end = end.next;
    }
    k = k % n;
    if (k == 0) {
    return head;
    }
    // 将链表变成循环结构
    end = head;
    while (end.next != null) {
    end = end.next;
    }
    end.next = head;
    // 找到断点前面的节点
    int pos = n - k;
    ListNode current = head;
    for (int i = 0; i < pos; i++) {
    current = current.next;
    }
    // 断开current和current.next
    ListNode nextNode = current.next;
    current.next = null;
    // 将nextNode连接到链表的头节点后面
    nextNode.next = head;
    return head;
    }
    }

    代码解释

  • 计算链表长度:通过遍历链表,计算其长度n。
  • 处理k的大小:对k取模,确保k在有效范围内。如果k为0,直接返回原链表。
  • 循环连接:将链表的最后一个节点连接到链表的第一个节点,形成循环结构。
  • 确定断点位置:计算断点前面的位置pos = n - k。
  • 找到断点前面的节点:从链表头开始,遍历pos次,找到断点前面的节点current。
  • 断开和重新连接:断开current与其下一个节点的连接,然后将断点后的节点连接到链表的头节点的后面,形成新的链表结构。
  • 通过上述步骤,链表将被向右旋转k个位置,得到所需的新链表结构。

    上一篇:BSTIterator-二叉搜索树迭代器
    下一篇:NestedIterator-扁平化嵌套列表迭代器

    发表评论

    最新留言

    网站不错 人气很旺了 加油
    [***.192.178.218]2025年05月02日 19时47分13秒