旋转链表

问题描述

给定一个链表,旋转链表,将链表每个节点向右移动 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<int> vec中。
  • 对特殊情况进行判断,链表为空,vec.size()==0) return nullptr,向右移动0步,直接return head
  • 按照题目要求,将移动后的元素存到一个新的vector<int> 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;
    }
};

标签: none

已有 2 条评论

  1. 我给你一个其他思路,你可以建立两个指针和一个变量,
    初始化时一个指向开始,一个指向第k个,然后两个指针的数值交换,
    知道第一个指针走到第k个位置的时候停止。
    这样程序的复杂度就只和k有关,与数组长度无关了,毕竟k一定小于整个数组长度。
    空间性能应该也会更好,不用开一个新的数组。

添加新评论