Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Rotate List

Leetcode algorithms 第 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.

解答

链表循环右移k位,首先k如果太大可以先模n,得到的结果是一样的,因为右移n位等于没有移位。

右移k位,只需要把倒数第k个节点开始的子链表和前面的子链表互换即可,使用两个指针找到倒数第k个节点的前一个节点,然后修改指针的指向即可。

具体代码如下:

/**
 * 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) {
        if (head == NULL) return NULL;
        
        int len = 1; //链表长度
        ListNode *last = head; //最后一个节点
        while (last->next != NULL) last = last->next, len++;
        
        k %= len; 
        if (k == 0) return head;
        
        ListNode *slow = head, *fast = head;
        for (int i = 0; i <= k; i++) //slow位置0,fast位置k+1
            fast = fast->next;
        while (fast != NULL)         //slow位置n-k-1,fast位置n
            fast = fast->next, slow = slow->next;
        
        ListNode *ans = slow->next; //slow的next为新的头
        slow->next = NULL;
        last->next = head;
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论