基本思路:
- 先求链表长度n,然后
k = k mod n
- 将链表首尾相连
- 找到新的head的前一个节点,断链,返回新head
代码如下:
// // Created by jt on 2020/9/26. // class Solution { public: /** * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ ListNode* rotateRight(ListNode* head, int k) { // write code here // 如果只有0个或1个节点 if (!head || k == 0) return head; // 将k与链表长度取模 int n = 1; ListNode *p = head, *q = head; while (p->next) { ++n; p = p->next; } k %= n; k = n - k; // 找到新链表头节点的前一个节点 while (--k > 0) { q = q->next; } // 合链 p->next = head; // 断链 ListNode *newHead = q->next; q->next = nullptr; return newHead; } };