61. 旋转链表

悠悠 2022-10-17 04:18 152阅读 0赞

> 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70][]

**k 是 链表长度的整数倍：链表不会发生位置变化。  
kk 不是 链表长度 的整数倍：实际移动位数是k%5 的值。**

> **  首先判断k%n(链表长度)**
> 
> ** k%n==0则不动  
>   否则,移动k%n个位置**
> 
> **  然后最后一个节点指向第一个节点,组成循环列表  
>    找到第 n-k%n个节点,让他的next=null  相当于断开循环列表  并让头结点=他的下一个节点**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70 1][]

class Solution {
        public ListNode rotateRight(ListNode head, int k) {
            /**
            首先判断k%n(链表长度)
    
            k%n==0则不动
            否则,移动k%n个位置
    
            然后最后一个节点指向第一个节点,组成循环列表
            找到第 n-k%n个节点,让他的next=null  相当于断开循环列表  并让头结点=他的下一个节点
    
             */
    
             if(k==0||head==null||head.next==null){
                 return head;
             }
    
             //看下长度
             int size=1;
             ListNode temp=head;
             while(temp.next!=null){
                 temp=temp.next;
                 size++;
             }
             if(k%size==0){
                 return head;
             }
             //组成循环节点
             temp.next=head;
             //在第size-k%size断开
             int m=size-k%size; 
    
            
             while(--m>0){
                 head=head.next;
             }
              ListNode res=head.next;//要断开节点的下一个节点是结果的头结点
             head.next=null;//找到要断开的节点
             return res;
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70]: /images/20221014/e218d2f7942e4b109e022601ea37ed94.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70 1]: /images/20221014/40ba075a559d4a75b15c8f30b3cb48b3.png