首页 > 试题广场 >

旋转链表

[编程题]旋转链表

热度指数：5316 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定链表的头节点，旋转链表，将链表每个节点往右移动 k 个位置，原链表后 k 个位置的节点则依次移动到链表头。

即，例如链表： 1->2->3->4->5 k=2 则返回链表 4->5->1->2->3

数据范围：链表中节点数满足 $0 \le n \le 1000\$ ， $0 \le k \le 10^9 \$

示例1

输入

{1,2,3,4,5},2

输出

{4,5,1,2,3}

示例2

输入

{1,2,3},3

输出

{1,2,3}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

Java

୧⍢⃝୨

import java.util.*;

public class Solution {
    public ListNode rotateLinkedList (ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode p = dummyHead;
        ListNode q = p;
        while (k > 0) {
            q = q.next;
            k--;
            if (q == null) {
                q = p.next;
            }
        }
        while (q.next != null) {
            p = p.next;
            q = q.next;
        }
        ListNode newHead = p.next;
        p.next = null;
        q.next = dummyHead.next;
        return newHead;
    }
}

发表于 2024-11-04 11:17:16 回复(0)

Java

唐氏综合征

快慢指针做法：

① 使用 tmp 指针计算链表长度 cnt

② 抛去循环部分，计算出链表实际的卫衣长度 k

③ 快指针先跑 k 个位置，这样就确保快慢相差为 k 个位置

④ 快慢一起跑，等快指针到头的时候，慢指针就到了位移后的起点

⑤ 快指针指向原来的头部 head, 这样链表就成环了

⑥ 把指向慢指针节点的指针的下个节点置为 null, 断开环

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode rotateLinkedList (ListNode head, int k) {
        // write code here
        if (head == null || head.next == null)
            return head;

        ListNode slow = head, fast = head;

        ListNode preSlow = new ListNode(-1);
        preSlow.next = head;

        ListNode tmp = head;
        int cnt = 0;
        while (tmp != null) {
            tmp = tmp.next;
            cnt++;
        }

        k %= cnt;

        if (k == 0) return head;

        for (int i = 0; i < k - 1; i++) fast = fast.next;

        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
            preSlow = preSlow.next;
        }
        // 断开
        preSlow.next = null;
        // 拼接
        fast.next = head;
        // 返回新头部
        return slow;
    }
}

发表于 2024-08-22 17:27:07 回复(0)

Java

牛客872923867号


import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode rotateLinkedList (ListNode head, int k) {
        // write code here
        if(head == null){
            return head;
        }

        int length = 0;
        ListNode fast = head;
        //统计链表长度
        while(fast != null){
            fast = fast.next;
            length++;
        }

        System.out.print(length);

        k = k % length;
        //移动次数和链表长度一致，就不用移动，直接返回链表即可
        if(k == 0){
            return head;
        }



        fast = head;
        ListNode slow = head;
        //快慢指针，fast先移动k步
        while(k != 0){
            fast = fast.next;
            k--;
        }

        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }
        
        //此时fast在链表末尾，slow.next 指向要旋转的链表
        ListNode node = slow.next;
        slow.next = null;

        fast.next = head;
        head = node;

        return head;

    }
}

发表于 2024-07-28 11:59:28 回复(0)

Java

木3吉吉

public ListNode rotateLinkedList(ListNode head, int k) {
    // write code here
    if (head == null)
        return null;

    ListNode len_acc = head;
    int len = 0;
    ListNode pre = head;
    ListNode tail = pre;

    //求链表长度，算旋转距离
    while (len_acc !=null){
        len++;
        len_acc = len_acc.next;
    }
    k = k%len;

    //找到距离为k的两个指针
    while(k > 0){
        tail = tail.next;
        k--;
    }
    //同时右移两个指针到链表末尾
    while (tail.next != null){
        pre = pre.next;
        tail = tail.next;
    }

    //重新连接链表
    ListNode temp = head;
    head = pre.next;
    tail.next = temp;
    pre.next = null;
    return head;
}

发表于 2024-05-08 22:27:33 回复(0)

Java

牛客148901号

public ListNode rotateLinkedList (ListNode head, int k) {
        if (head == null || head.next == null || k <= 0) {
            return head;
        }

        int length = 1;
        ListNode curr = head;
        while (curr.next != null) {
            length++;
            curr = curr.next;
        }

        curr.next = head;
        k = k % length;
        if (k == 0) {
            return head;
        }

        for (int i = 0; i < length-k-1; i++) {
            head = head.next;
        }
        ListNode newHead = head.next;
        head.next = null;
        return newHead;
    }

发表于 2024-04-27 18:27:38 回复(0)

Java

礼堂纯真丁一郎

public ListNode rotateLinkedList (ListNode head, int k) {
        // write code here
        ListNode res = new ListNode(0);
        res.next = head;
        ListNode fast = res;
        ListNode front = null;
        ListNode slow = res;
        ListNode cur = head;
        int length = 1;
        if ( head == null || head.next == null) return head;
        //判断链表长度
        while (cur.next != null) {
            length++;
            cur = cur.next;
        }
        //对长度进行取余得到有效变换的长度
        int j = k % length;
        for (int i = 0; i < j; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            front = slow;
            slow = slow.next;
            fast = fast.next;
        }
        front.next = null;
        res.next = slow;
        while (slow.next != null) {
            slow = slow.next;
        }
        slow.next = head;
        return res.next;
    }

发表于 2024-04-10 17:07:43 回复(0)

Java

pein531

其实就是求链表的倒数第k个节点，然后以它为头结点返回，把原始链表的尾连接上原始链表的头。但是这个k可能比原始链表要大，所以得先求出链表的长度，然后k对链表长度取余再进行算法流程。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode rotateLinkedList (ListNode head, int k) {
        if(head == null) return head;
        // 先求链表倒数第k个节点
        ListNode cur = head;
        int n = 0;
        while(cur != null){
            n ++;
            cur = cur.next;
        }
        k %= n;
        ListNode fast = head;
        for(int i = 0; i < k - 1; i++){
            fast = fast.next;
        }
        ListNode slow = head;
        ListNode prev = new ListNode(-1);
        prev.next = slow;
        while(fast.next != null){
            prev = prev.next;
            slow = slow.next;
            fast = fast.next;
        }
        prev.next = null;
        fast.next = head;
        return slow;
    }
}

发表于 2021-12-15 18:18:20 回复(2)