【Leetcode】61. Rotate List（链表）

青旅半醒 2022-02-27 03:58 156阅读 0赞

Given a linked list, rotate the list to the right by *k* places, where *k*is non-negative.

**Example 1:**

Input: 1->2->3->4->5->NULL, k = 2
    Output: 4->5->1->2->3->NULL
    Explanation:
    rotate 1 steps to the right: 5->1->2->3->4->NULL
    rotate 2 steps to the right: 4->5->1->2->3->NULL

**Example 2:**

Input: 0->1->2->NULL, k = 4
    Output: 2->0->1->NULL
    Explanation:
    rotate 1 steps to the right: 2->0->1->NULL
    rotate 2 steps to the right: 1->2->0->NULL
    rotate 3 steps to the right: 0->1->2->NULL
    rotate 4 steps to the right: 2->0->1->NULL

题目大意：

将链表向右平移k各位置。

解题思路：

k可以化简为k=k%n（n为链表的长度），需要注意当n==0时和k==0时，应直接输出头指针；之后，我们将链表分为两个部分，可以抽象成将后半部分放到前面，所以我们需要计算出前半部分和后半部分的起始、终止位置。

对于前半部分其结束位置与起始位置相差(n-k-1)。

8 ms, faster than 100.00% of C++ online submissions for Rotate List.

class Solution {
    public:
        ListNode* rotateRight(ListNode* head, int k) {
            int n= 0;
            ListNode *p_l, *p_r, *h_l, *h_r;
            p_l = head;
            p_r = head;
    		while(head){
            	n++;
            	head = head->next;
    		} 
            if(n == 0){
                return p_l;
            }
            
            k = k % n;
            
            if(k==0)
                return p_l;
    
            for(int i=0; i<(n-k-1); i++){
            	p_r = p_r->next;
    		}    
            
            h_l = p_r->next;
            h_r = p_r->next;
    		while(h_r->next){
    			h_r = h_r->next;
    		} 
    
    		h_r->next = p_l;
    		p_r->next = NULL;
            
            return h_l;
        }
    };