[LeetCode] Rotate List 单项链表旋转

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.

Hide Tags

 Linked List Two Pointers

 

---

    这题有点难理解，k 的意思是链表右起第k 个，k 大于链的个数时候，循环读取，所以题目中k =5 的时候直接返回。思路是确定链表断开的地方，有个技巧是一个快指针先遍历k 次，然后快慢指针再一次遍历，如果快指针到尾了，这时候慢指针后于快指针k 次，刚好是右起k 步。

 

#include <iostream>
using namespace std;

/**
 * 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||k==0)  return head;
        int cnt =0;
        ListNode * first=head,*slow=head;
        while(cnt<k){
            if(first==NULL) first = head;
            first=first->next;
            cnt++;
        }
        if(first==NULL) return head;
        while(first->next!=NULL){
            first=first->next;
            slow=slow->next;
        }
        first->next=head;
        head = slow->next;
        slow->next = NULL;
        return head;
    }
};

int main()
{

    return 0;
}