【LeetCode】61. 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.

解题思路

先遍历一遍确定链表中元素的个数n，然后k对n求模，因为移动n的倍数还是链表本身。 然后找到倒数第k个，这个就是移动之后的新的链表头。

AC代码

/** * 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) return head; int n = 1; ListNode *tail = head; while (tail->next != NULL) { n += 1; tail = tail->next; } k = k % n; if (k == 0) return head; // 将当前链表的尾的下一个元素指向开头 tail->next = head; //找到倒数第k个，作为移动后的头元素，它的前一个就是队尾，设其next为null for (int i = 1; i < n- k; ++i) { head = head->next; } ListNode* ans = head->next; head->next = NULL; return ans; } };