61. 旋转链表


给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL


思路: 环链表法
计算链表的长度N。

k对N取模。 r=k%N。

当 r == 0 时,不需要旋转。

当 r > 0 时,右移r个节点即可。

将链表的尾部指向头部,构成循环链表。并在从开始的N-r个节点后面将链表断开。第N-r+1个节点就是新的头节点。

例如:1->2->3->4->5->NULL, k = 2

链表长度N=5. 尾部连到头部构成环。 1->2->3->4->5->

r=k%N=2%5=2. 右移2个节点。在第N-r=5-2=3个节点后面断开,第N-r+1=5-2+1=4节点就是新的头节点。

 public ListNode rotateRight(ListNode head, int k) {
        if(head==null)
            return null;
        int len=1;
        ListNode tem=head;
        while(tem.next!=null)//第一次遍历找到长度和尾结点
        {
            len++;
            tem=tem.next;
        }
        tem.next=head;//首尾相连组成循环链表
        int btnum=k%len;//真正需要右移的次数
        ListNode interruptNode=head;    
        for (int i = 0; i < len - btnum-1; i++) {//第二次遍历找到断开节点
            interruptNode=interruptNode.next;
        }
        ListNode res=interruptNode.next;
        interruptNode.next=null;
        return res;
    }

提交记录

231 / 231 个通过测试用例
状态:

通过

执行用时:1 ms
提交时间:1 小时,33 分钟之前
  • 作者:低调做个路人 (扫码联系作者)
  • 发表时间:2019-12-03 05:35:34
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 评论