旋转链表__牛客网

C++

牛客541678616号

循环一次，记录要操作的地址和链表长度

然后操作就好了

本题要求不高，所以我嫌麻烦直接开了个数组记（其实只记要用的几个地址就够了）

class Solution {
public:

    ListNode* rotateLinkedList(ListNode* head, int k) {
        int len=0;
        ListNode* address[1010];
        ListNode *cur=head;
        while (cur) 
        {
            address[len++]=cur;
            cur=cur->next;
        }
        if(len==0)
            return head;

        k%=len;

        address[len-k-1]->next=nullptr;
        address[len-1]->next=head;
        return address[len-k];
    }
};

发表于 2023-03-05 21:13:40 回复(1)

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)

GG程序员

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 (k == 0 || head == null) return head;
        ListNode tail = head; // 找到尾部
        int length = 1; // 计算链表长度
        while(tail.next!=null) {
            tail = tail.next;
            length++;
        }
        k = k % length; // 这里的操作是因为 k 可能大于length 所以要求余
        ListNode newHeadPre = head; // 新链头的上一个位置
        for (int i = 0; i < length - k - 1; i++) {
            newHeadPre = newHeadPre.next;
        }
        ListNode newHead = head; // 新链头
        newHead = newHeadPre.next; // 更新新链头
        newHeadPre.next = null; // 将新链头的上一个位置 设置位链尾
        tail.next = head; // 将原本的链尾，接到老的链头上

        return newHead;
    }
}

这个还是很好懂的

发表于 2024-05-23 00:12:17 回复(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)

C

StellarVibes

struct ListNode* rotateLinkedList(struct ListNode* head, int k ) {

if(head==NULL)

{

return NULL;

}

struct ListNode* head1=head;

int len = 1;

while(head1->next)

{

head1=head1->next;

len++;

}

if(len==1)

{

return head;

}

k%=len;

head1->next=head;

int n = len-k;

struct ListNode* prev=NULL;

while(n)

{

prev=head;

head=head->next;

n--;

}

prev->next=NULL;

return head;

}

发表于 2024-03-31 22:36:45 回复(1)

香草XxiangChao

package main

import (

//"fmt"

. "nc_tools"

)

/*

* type ListNode struct{

* Val int

* Next *ListNode

* }

*/

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* @param head ListNode类

* @param k int整型

* @return ListNode类

*/

func rotateLinkedList(head *ListNode, k int) *ListNode {

// 处理空链表或单个节点的情况

if head == nil || head.Next == nil || k == 0 {

return head

}

// 计算链表长度

length := 0

cur := head

var tail *ListNode

for cur != nil {

if cur.Next == nil {

tail = cur

}

length++

cur = cur.Next

}

k = k % length

cur = head

var pre *ListNode

var step int = 1

for step <= length-k {

step++

pre = cur

cur = cur.Next

}

//fmt.Println(cur.Val, pre.Val, tail.Val, head.Val)

pre.Next = nil

tail.Next = head

return cur

}

发表于 2025-09-21 21:32:44 回复(0)

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)

Rust

老刘001

/**
 *  #[derive(PartialEq, Eq, Debug, Clone)]
 *  pub struct ListNode {
 *      pub val: i32,
 *      pub next: Option<Box<ListNode>>
 *  }
 * 
 *  impl ListNode {
 *      #[inline]
 *      fn new(val: i32) -> Self {
 *          ListNode {
 *              val: val,
 *              next: None,
 *          }
 *      }
 *  }
 */
struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param head ListNode类 
        * @param k int整型 
        * @return ListNode类
    */
    pub fn rotateLinkedList(&self, mut head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
        // write code here
        if head.is_none() {return head}
        let mut len = 0;
        let mut p = &head;
        while p.is_some() {
            p = &p.as_ref().unwrap().next;
            len += 1;
        }
        let mut skip = len - (k % len);
        if (k % len) == 0 {return head}
        drop(p);
        let mut p = &mut head;
        for _ in 1..skip {
            p = &mut p.as_mut().unwrap().next;
        }
        let mut newhead = p.as_mut().unwrap().next.take();
        drop(p);
        let mut p = &mut newhead;
        while p.as_mut().unwrap().next.is_some() {
            p = &mut p.as_mut().unwrap().next;
        }
        p.as_mut().unwrap().next = head;
        newhead
        
        // todo!();
    }
}

发表于 2024-08-15 23:00:31 回复(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)

牛客183275086号

/**

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* @param head ListNode类

* @param k int整型

* @return ListNode类

*/

struct ListNode* rotateLinkedList(struct ListNode* head, int k ) {

// write code here

if(head == NULL || head->next == NULL || k == 0)

{

return head;

}

int len = 1;

struct ListNode* temp = head;

while(temp->next != NULL)

{

temp = temp->next;

len++;

}

k = k % len;

if (k == 0) {

return head;

}

struct ListNode *new_head_prev = head;

for (int i = 0; i < len - k - 1; i++) {

new_head_prev = new_head_prev->next;

}

// 旋转链表

struct ListNode *new_head = new_head_prev->next;

new_head_prev->next = NULL;

temp->next = head;

return new_head;

}

发表于 2024-07-13 16:24:40 回复(0)

Python3

liangzhengjie

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param k int整型 
# @return ListNode类
#
class Solution:
    def rotateLinkedList(self , head: ListNode, k: int) -> ListNode:
        # write code here
        l_len = 0
        point = head
        while point is not None:
            l_len += 1
            point = point.next
        if l_len == 0:
            return head

        k = k%l_len
        if k == 0:
            return head

        point = head
        next_point = point
        for i in range(k):
            next_point = next_point.next

        while next_point.next is not None:
            next_point = next_point.next
            point = point.next

        new_head = point.next
        point.next = None
        next_point.next = head
        return new_head

发表于 2024-05-29 23:16:40 回复(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)

Python 3

水彩笔watercol

class Solution:
    def rotateLinkedList(self , head: ListNode, k: int) -> ListNode:
        if head == None:
            return head
        rare = head
        length = 1
        while rare.next != None:
            rare = rare.next
            length = length + 1 
        rare.next = head
        step = length - k % length
        while step > 1:
            head = head.next
            step = step - 1
        p = head
        head = head.next
        p.next = None
        return head

发表于 2024-05-06 21:17:06 回复(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)

C++

yooho_

1. 根据之前所学的链表反转的方法；可以先将链表整个反转；

2. 然后遍历计数，在k位置断开（也就是令节点为空，令为空前先记录一下后半段的链表开始）把链表分为前半段和后半段，是独立的两个链表，针对对立的两个链表再做链表反转；

3. 最后将第1个的为与第二个链表的头想连接即可

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    //链表反转
    ListNode* reverse(ListNode* head) {
        ListNode* h = new ListNode(0);
        ListNode* temp;
        while (head != nullptr) {
            temp = head;
            head = head->next;
            temp->next = h->next;
            h->next = temp;
        }
        return h->next;
    }
    ListNode* rotateLinkedList(ListNode* head, int k) {
        // write code here
        if(head==nullptr) return nullptr;
        int n = 0;
        int cnt = 0;
        //把整个链表反转
        head = reverse(head);
        ListNode* h = head;
        //计算整个链表长度，因为k有可能大于n
        while (h != nullptr) {
            h=h->next;
            n++;
        }
        
        //k取模
        k%=n;
        
        ListNode* end=head;
        while (end != nullptr) {
            cnt++;
            if (cnt == k) {//找到断开位置
                break;
            }
            end=end->next;
        }
        //断开位置的下一个就是第二个链表的起始位置
        ListNode* secondstart=end->next;
        //链表断开
        end->next=nullptr;
        //对第一个链表进行反转
        ListNode* first=reverse(head);
        ListNode* ans=first;
        //找到第一个链表的尾部（且不为空）
        while(first->next!=nullptr){
            first=first->next;
        }
        //对第二个链表进行反转
        secondstart=reverse(secondstart);
        //cout<<secondstart->val<<" "<<secondstart->next->val;
        //将第一个链表的尾部和第二个链表的头相连接
        first->next=secondstart;
        return ans;
    }
};

发表于 2024-04-27 17:15:24 回复(0)

C++

虚数五行区

遍历

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* rotateLinkedList(ListNode* head, int k) {
        // write code here
        // 算出节点数量
        ListNode* temp = head;
        int len = 0;
        while(temp)
        {
            temp = temp->next;
            ++len;
        }

        k %= len;
        if(k==0 || head==nullptr)
            return head;

        // 新链表头的前一个
        ListNode* t_1 = head;
        // 新链表头
        ListNode* t_2 = head;
        // 原来链表的最后一位
        ListNode* t_3 = head;
        // 从下标 1 开始
        int t = 1;
        while(t<len)
        {
            // 新链表头的前一个
            if(t<len-k)
                t_1 = t_1->next;
            // 新链表头
            if(t<=len-k)
                t_2 = t_2->next;
            // 原来链表的最后一位
            t_3 = t_3->next;
            ++t;
        }

        // cout << t_1->val << ", " << t_2->val << ", " << t_3->val << endl;

        t_1->next = nullptr;
        t_3->next = head;
        
        return t_2;
    }
};

发表于 2024-04-25 18:35:51 回复(0)

C++

_WJJ

确定倒数第k个节点就好了

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

int num = 0;
while(pre){
num++;
pre = pre->next;
}
int restnum = k % num;
if(restnum == 0 || head == nullptr)return head;

for (int i = 0; i < num - restnum - 1; i++) {
topk = topk->next;
}
if (topk) {
ListNode* tempk = topk->next;
pre = tempk;
topk->next = nullptr;
while (tempk) {
if (tempk->next == nullptr) {
tempk->next = head;
break;
} else {
tempk = tempk->next;
}
}
return pre;
}
else{
return head;
}
}
};

编辑于 2024-04-19 16:30:52 回复(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)

晚梦忆笙歌

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
        int num = getNodeNum(head);
        if (num == 0 || k % num == 0) return head;
        k = k % num;
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode fast = dummyHead;
        while (k-- > 0) {
            fast = fast.next;
        }
        ListNode slow = dummyHead;
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        ListNode rotateHead = slow.next;
        slow.next = null;
        fast.next = dummyHead.next;
        return rotateHead;
    }

    public int getNodeNum(ListNode head) {
        int res = 0;
        while (head != null) {
            res++;
            head = head.next;
        }
        return res;
    }
}

编辑于 2023-12-18 13:41:41 回复(0)

布鲁克11

if(head==NULL)//空链表的特殊情况
            return head;
        struct ListNode * p=head;
        int length=0;
        while(p)//遍历链表求表长
        {
            p=p->next;
            length++;
        }
        p=head;
        while(p->next)//遍历链表找到表尾
        {
            p=p->next;
        }
        p->next=head;//使链表成为循环链表
        p=head;
        for(int i=0;i<length-k%length;i++)//找到旋转后的表头
        {
            p=p->next;
        }
        struct ListNode * result=p;
         for(int i=0;i<length-1;i++)
        {
            p=p->next;
        }
        p->next=NULL;//遍历新链表使表尾指针指空，接触循环链表
        return result;

发表于 2023-04-25 17:22:53 回复(0)

旋转链表

输入

输出

输入

输出

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

问题信息

热门推荐

通过挑战的用户

相关试题