leetcode---61. 旋转链表

我就是我 2023-02-23 08:15 5阅读 0赞

给定一个链表，旋转链表，将链表每个节点向右移动 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

思路：每个节点都向右移动，需要考虑k>n和看k<n两种 ，当k>n的时候实际移动效果和k%n的次数是一样的。所以我们统一按照k%n来考虑。 向右移动实际就是将倒数k个拿掉挂到前面。这个时候需要注意的是旋转后的链表

1、头指针指向改变

2、新的尾结点需要指向为空。

那么如何找头和尾，将倒数k个挂在原来的头，那么倒数第k个(正着数就是第n-k+1)就是新链表的头 倒数第k+1(n-k)个就是新链表的尾巴。

首先第一步求出链表的长度，然后从head开始走n-k-1步到达第n-k个结点，找到新的尾巴和新的头。

public ListNode rotateRight(ListNode head, int k) {
            if (null == head || null == head.next) {
                return head;
            }
            ListNode cur = head;
            int n = 1;
            while (null != cur.next) {
                cur = cur.next;
                n++;
            }
            //成环 首尾相连
            cur.next = head;
            //倒数第k个是正数第n-k+1,这个将会是旋转后的第一个结点 head指向它 正数第n-k个是旋转后的尾结点
            ListNode new_tail = head;
            for (int i = 0; i < (n - k % n) - 1; i++) {
                new_tail = new_tail.next;
            }
            //找到新的头
            ListNode new_head = new_tail.next;
            //新的尾结点指向null
            new_tail.next = null;
            return new_head;
        }