首页 > 代码库 > [C++]LeetCode: 76 Rotate List

[C++]LeetCode: 76 Rotate List

2024-10-27 13:10:03   208人阅读

题目：

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步进行旋转，得到新的链表。

Given [0,1,2], rotate 1 steps to the right -> [2,0,1].

Given [0,1,2], rotate 2 steps to the right -> [1,2,0].

Given [0,1,2], rotate 3 steps to the right -> [0,1,2].

Given [0,1,2], rotate 4 steps to the right -> [2,0,1].

方法：先成环，再断开链表。

思路：由于旋转的节点数k可能为0，也可能超过链表的长度，所以我们需要对k取余。

游标指针从头节点向后移动，当指向尾节点时，得到链表长度len；然后将链表头尾相连，接着游标再向后移动 k % len 步得到结果链表的尾节点。最后将head指向结果尾部节点的下一个节点，再断开链表（尾部节点->next置NULL）

Attention：

1. 由于旋转后，我们并没有改变相对节点顺序（如1-2-3-4，k=2,变为3-4-1-2），所以可以先形成链表环，之后再要求位置断开。这种方法十分巧妙，应该学习。（此时，p指向原链表最后一个节点）

 //(2) 让链表头尾相连
        p->next = head;

2. 需要考虑k的不同取值，k = 0, k<=len, k> len, 取余得到相对旋转位置。

//(3) 找到结果链表的尾节点
        k %= len;
        int step = len - k;
3. 注意初始时，如果链表无节点，返回head, 排除特殊情况。

 if(head == NULL) return head;
复杂度：O(N)


AC Code:

/**
 * 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 head;
        ListNode* p = head;
        int len = 1;
        //(1) 计算链表长度
        while(p->next != NULL)
        {
            p = p->next;
            len++;
        }
        
        //(2) 让链表头尾相连
        p->next = head;
        
        //(3) 找到结果链表的尾节点
        k %= len;
        int step = len - k;
        while(step > 0)
        {
            p = p->next;
            step--;
        }
        
        //(4) 断开链表，从结果链表的尾节点位置 新的头结点，是结果链表尾节点的下一个结点。结果链表尾节点->next 置NULL
        head = p->next;
        p->next = NULL;
        
        return head;
    }
};


[C++]LeetCode: 76 Rotate List


联系
我们