【LeetCode】61. Rotate List解法及分析

忘是亡心i 2022-07-26 05:20 99阅读 0赞

**61. Rotate List**

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:  
Given `1->2->3->4->5->NULL` and k = `2`,  
return `4->5->1->2->3->NULL`.

【分析】

这个题相对简单，几乎不涉及任何算法，对链表指针熟悉的话，很容易完成，不过需要注意一些**细节**：1.如何求链表的长度；2. k>链表长度时如何处理；3. 指针交换逻辑顺序。

【解法及注释】

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* rotateRight(ListNode* head, int k) {
            
            ListNode *phead=head;
            ListNode *pTail=head;
            ListNode *temp;
            
            if(head==NULL)return head;
            
            int length=1;//初始化节点个数
            while(pTail->next!=NULL)//pTail指向原链表的尾节点
            {
               pTail=pTail->next;
               length++;
            }
            k=k%length;//k>=length的情况，视做“环”
            if(k==0)return head;
            
            for(int i=0;i<length-k-1;i++)//phead指向旋转节点
            {
                phead=phead->next;
            }
            temp=phead->next;//指向旋转位置的下一个节点,即旋转后的头结点
            phead->next=NULL;//旋转后指向空
            pTail->next=head;//原先的尾节点指针指向头结点
           
            return temp;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，99人围观）

还没有评论，来说两句吧...

相关阅读

相关 rotate list java_Rotate List leetcode java

题目： Given a list, rotate the list to the right by k places, where k is non-negative. F

柔情只为你懂/ 2022年11月03日 04:08/ 0 赞/ 104 阅读

相关 LeetCode61——Rotate List

LeetCode61——Rotate List 简单的链表操作。维护head和r指针，r初始指向链表末尾，并且r-next=head; 首尾相接，再根据给定K移动特定指针。

Love The Way You Lie/ 2022年08月09日 12:57/ 0 赞/ 121 阅读

相关【leetcode每日一题】61.Rotate List

题目： Given a list, rotate the list to the right by k places, where k is non-negative. F

梦里梦外;/ 2022年08月04日 14:37/ 0 赞/ 121 阅读

相关 leetcode 61. Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative. For ex

亦凉/ 2022年07月29日 09:20/ 0 赞/ 161 阅读

相关【LeetCode】61. Rotate List解法及分析

61. Rotate List Given a list, rotate the list to the right by k places, where k is n

忘是亡心i/ 2022年07月26日 05:20/ 0 赞/ 100 阅读

相关【LeetCode】48. Rotate Image解法及注释

48. Rotate Image You are given an n x n 2D matrix representing an image. Rotate the i

小咪咪/ 2022年07月26日 01:46/ 0 赞/ 347 阅读

相关 LeetCode 61.Rotate List (旋转链表)

题目描述：给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。示例 1: 输入: 1->2->3->4->5->NULL, k =

╰半橙微兮°/ 2022年05月10日 05:28/ 0 赞/ 162 阅读

相关【Leetcode】61. Rotate List（链表）

Given a linked list, rotate the list to the right by k places, where kis non-negative.

青旅半醒/ 2022年02月27日 03:58/ 0 赞/ 132 阅读

相关 61. Rotate List

class Solution { public ListNode rotateRight(ListNode head, int k) {

拼搏现实的明天。/ 2021年12月22日 06:51/ 0 赞/ 186 阅读

相关 [LeetCode] Rotate List 旋转链表

Given a list, rotate the list to the right by k places, where k is non-negative. For ex

快来打我*/ 2021年09月19日 10:16/ 0 赞/ 249 阅读