首页 > 代码库 > LeetCode61 Rotate List

LeetCode61 Rotate List

题目:

Given a list, rotate the list to the right by k places, where k is non-negative. (Medium)

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

分析:

利用双指针,一个指针先走k步,然后两个指针同时走,runner走到链表尾时chaser在要翻转之前位置,然后折腾一下指针指向即可。

注意:如果k 大于指针长度时,题目表述不清,应该是按照循环回来处理。所以前面需要求一下链表长度,并把k % size。

代码:

 1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode* rotateRight(ListNode* head, int k) {12         if (head == nullptr) {13             return nullptr;14         }15         int size = 0;16         ListNode* temp = head;17         while (temp != nullptr) {18             temp = temp -> next;19             size++;20         }21         k = k % size;22         ListNode* runner = head;23         ListNode* chaser = head;24         for (int i = 0; i < k; ++i) {25             runner = runner -> next;26         }27         while (runner -> next != nullptr) {28             runner = runner -> next;29             chaser = chaser -> next;30         }31         runner -> next = head;32         ListNode* result = chaser -> next;33         chaser -> next = nullptr;34         return result;35     }36 };

 

 

LeetCode61 Rotate List