Rotate List

发表于 | 分类于

Rotate List

题目描述：

给定一个链表的头节点和一个整数k，其中整数k表示从尾部向左k个节点进行旋转。要求返回旋转后的链表头结点。

例子：

具体描述见LeetCode61。

解题思路：

主要是通过将链表连接成环状，然后通过和链表长度的比较找到目标节点断开链表。主要注意的是：在链表中有时候可以通过连接成环来处理问题；问题中k可以大于链表长度的情况的处理，通过求余即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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) return head;
        // 空节点直接返回
        int length = 1;
        ListNode* cur = head;
        while(cur->next){
            cur = cur->next;
            length++;
        }
        // 计算出链表的长度
        cur->next = head;
        // 将链表连接成环状
        if (k %= length){
        // 当k大于链表的长度的时候
            for (auto i = 0; i < length - k; i++)
                cur = cur->next;
                //找到需要断开的位置
        }
        ListNode* newhead = cur->next;
        cur->next = NULL;
        //断开并且修改尾部节点指向
        return newhead;
        
        
    }
};