旋转链表

[编程题]旋转链表

热度指数：4046 时间限制：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

木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 回复(0)