leetcode | Rotate List

Rotate List ：https://leetcode.com/problems/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（没必要做无用功）；

解法一

由如何取得倒数的第k个节点可类比得到如下算法：
先让 q 从头跑 k 步；然后让 p, q 一起跑，q 到达链表尾部时，p 为倒数第 k 个节点。
算法时间复杂度：$O(n)$， 空间复杂度$O(1)$

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
//算法时间复杂度：$O(n)$， 空间复杂度$O(1)$
class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if (head == NULL || head->next == NULL)return head;int N = Size(head);k = k % N;ListNode dummy(0);dummy.next = head;ListNode* p = &dummy;ListNode* q = &dummy;for (int i = 0; i < k; i++) {q = q->next;}while (q->next != NULL) {p = p->next;q = q->next;}q->next = dummy.next;dummy.next = p->next;p->next = NULL;return dummy.next;}
private:int Size(ListNode* head) {int i = 0;while (head) {i++;head = head->next;}return i;}
};

解法二

将链表头尾相连，组成一个圈，那么从头开始跑 N-k 步，然后此处断开，即为所求
算法时间复杂度：$O(n)$， 空间复杂度$O(1)$

    //算法时间复杂度：$O(n)$， 空间复杂度$O(1)$ListNode* rotateRight(ListNode* head, int k) {if (head == NULL || head->next == NULL)return head;int N = 1;ListNode* p = head;while (p->next != NULL) {N++;p = p->next;}p->next = head;k = k % N;for (int i = 0; i < N-k; i++) { // p 从 head->prev 继续跑p = p->next;}//断开环head = p->next;p->next = NULL;return head;      }