61、旋转链表

  1. 示例 1:
  2. 示例 2:
    1. 解释:
  3. 代码

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

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    // 循环右移
    public ListNode rotateRight(ListNode head, int k) {
        int len = 0;
        ListNode p = head;
        if (head == null) return head;
        while(p!=null) {
            len++;
            p = p.next;
        }
        if (k % len == 0) {
            return head;
        }
        p = new ListNode(-1);
        p.next = head;
        ListNode q = null;// 标记分离的节点
        // 先移动len-k%len +1 步,移动到旋转的最后一个元素的前一个元素处
        for (int i = 0;i < len - k % len + 1;i++){
            q = p;
            p = p.next;
        }
        // 此时p元素将成为头节点
        while (p.next != null) {
            p = p.next;
        }
        p.next = head;
        head = q.next;
        q.next = null;
        return head;
    }
}

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 1056615746@qq.com

文章标题:61、旋转链表

字数:337

本文作者:攀登

发布时间:2020-07-26, 00:19:44

最后更新:2024-06-15, 15:52:32

原始链接:http://jiafeimao-gjf.github.io/2020/07/26/61%E3%80%81%E6%97%8B%E8%BD%AC%E9%93%BE%E8%A1%A8/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

×

喜欢就点赞,疼爱就打赏