首页 > itarticle > leetcode-61-rotate list

leetcode-61-rotate list

admin 11月 12, 2020 0

题目

链表右移

分析

对于给定的链表，右移k位
举例说明：
输入1->2->3->4->5->NULL and k = 2,
输出4->5->1->2->3->NULL.
解析：
右移k位，即返回以(len(list) - k%len(list))开始，以他的前一位结束的链表

C++代码实现


 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* (ListNode* head, int k) {
        if(!head || k == 0)
        	return head;
        
        // Find the length of head
        int len = 1;
        ListNode* p = head;
        while(p->next != NULL){
        	len++;
        	p = p->next;
        }

        p->next = head;  // To be a ring
        int x = len - k % len;   //Very import. For the case that k>len
        for(int i = 0; i < x; i++){
        	p = p->next;
        }

        head = p->next;
        p->next = NULL;
        return head;
    }
};