旋转链表

问题描述

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-list

思路

• 首先将链表存到vector vec中。
• 对特殊情况进行判断，链表为空，vec.size()==0) return nullptr，向右移动0步，直接return head
• 按照题目要求，将移动后的元素存到一个新的vector tmp中
• 根据tmp建立一个新的链表，并返回其头节点

题解

class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        vector<int> vec;
        ListNode *cur = head;
        while (cur != nullptr) {
            vec.push_back(cur->val);
            cur = cur->next;
        }
        if(vec.size()==0)  return nullptr;
        if(k==0) return head;
        k = k % (vec.size());
        vector<int> tmp;
        for (int i = vec.size()-k; i < vec.size(); i++) {
            tmp.push_back(vec[i]);
        }
        for (int i = 0; i <vec.size()-k; i++) {
            tmp.push_back(vec[i]);
        }
        ListNode *p = nullptr;
        ListNode *newnode;
        for (int i = 0; i < tmp.size(); i++) {
            if (p == nullptr) {
                p=new ListNode(tmp[i]);
                newnode=p;
            } else{
                p->next= new ListNode(tmp[i]);
                p=p->next;
            }
        }
        return newnode;
    }
};