算法leetcode｜61. 旋转链表（rust重拳出击）

文章目录

61. 旋转链表：

给你一个链表的头节点

head

，旋转链表，将链表每个节点向右移动

k

个位置。

样例 1：

输入：
    
    head = [1,2,3,4,5], k = 2
    
输出：
    
    [4,5,1,2,3]

样例 2：

输入：
    
    head = [0,1,2], k = 4
    
输出：

    [2,0,1]

提示：

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

分析：

• 面对这道算法题目，二当家的再次陷入了沉思。
• 首先节点向右移动的位置 k 为0，我们什么都不需要做，直接返回原来的链表即可。
• 如果想要旋转链表，就必须知道链表的长度，所以我们先从头遍历一次链表，计算一下链表的长度，如果长度是0，同样我们什么都不需要做，也直接返回原来的链表即可。
• 在知道链表的长度 n 之后，我们就可以旋转链表了，但是节点向右移动位置 k 的值可能大于链表的长度 n ，这时候我们并不需要真移动 k 个位置，因为每移动 n 个位置，链表就会恢复原状，所以我们只需要移动 k % n 个位置，而如果这个值是0时，我们依然可以什么都不做直接返回原来的链表。
• 移动之后，链表的头和尾会发生变化，所以需要确定新的尾和头然后将他们断开，并且把旧的尾和头相连。

题解：

rust：

// Definition for singly-linked list.// #[derive(PartialEq, Eq, Clone, Debug)]// pub struct ListNode {//   pub val: i32,//   pub next: Option<Box<ListNode>>// }//// impl ListNode {//   #[inline]//   fn new(val: i32) -> Self {//     ListNode {//       next: None,//       val//     }//   }// }implSolution{pubfnrotate_right(mut head:Option<Box<ListNode>>, k:i32)->Option<Box<ListNode>>{if k ==0|| head.is_none(){return head;}// 链表的长度letmut n =0;letmut tail =&head;whileletSome(node)= tail {
            n +=1;
            tail =&node.next;}let add = n - k % n;if add == n {return head;}// 寻找新尾letmut tail =&mut head;for _ in1..add {
            tail =&mut tail.as_mut().unwrap().next;}// 新头和新尾断开letmut ans = tail.as_mut().unwrap().next.take();// 找到旧尾letmut tail =&mut ans;while tail.is_some()&& tail.as_ref().unwrap().next.is_some(){
            tail =&mut tail.as_mut().unwrap().next;}// 旧尾和旧头相连
        tail.as_mut().unwrap().next = head;return ans
    }}

go：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */funcrotateRight(head *ListNode, k int)*ListNode {if k ==0|| head ==nil|| head.Next ==nil{return head
    }// 链表的长度
    n :=1
    tail := head
    for tail.Next !=nil{
        tail = tail.Next
        n++}
    add := n - k%n
    if add == n {return head
    }// 成环
    tail.Next = head

    // 寻找新尾for add >0{
        tail = tail.Next
        add--}// 新头
    ans := tail.Next

    // 新尾和新头断开
    tail.Next =nilreturn ans
}

c++：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */classSolution{public:
    ListNode*rotateRight(ListNode* head,int k){if(k ==0|| head ==nullptr|| head->next ==nullptr){return head;}// 链表的长度int n =1;
        ListNode *tail = head;while(tail->next !=nullptr){
            tail = tail->next;
            n++;}int add = n - k % n;if(add == n){return head;}// 旧尾连旧头成环
        tail->next = head;// 寻找新尾while(add--){
            tail = tail->next;}// 新头
        ListNode *ans = tail->next;// 新尾和新头断开
        tail->next =nullptr;return ans;}};

python：

# Definition for singly-linked list.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclassSolution:defrotateRight(self, head: Optional[ListNode], k:int)-> Optional[ListNode]:if k ==0ornot head ornot head.next:return head
        # 确定链表的长度
        n =1
        tail = head
        while tail.next:
            tail = tail.next
            n +=1if(add := n - k % n)== n:return head
        # 旧尾连旧头成环
        tail.next= head
        # 寻找新尾while add:
            tail = tail.next
            add -=1# 新头
        ans = tail.next# 新尾和新头断开
        tail.next=Nonereturn ans

java：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */classSolution{publicListNoderotateRight(ListNode head,int k){if(k ==0|| head ==null|| head.next ==null){return head;}// 链表的长度int n =1;ListNode tail = head;while(tail.next !=null){
            tail = tail.next;
            n++;}int add = n - k % n;if(add == n){return head;}// 旧尾连旧头成环
        tail.next = head;// 寻找新尾while(add-->0){
            tail = tail.next;}// 新头ListNode ans = tail.next;// 新尾和新头断开
        tail.next =null;return ans;}}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~