Rotate List

https://leetcode.com/problems/rotate-list/description/

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.

Thoughts

右移k位先mod n, 确定实际是右移多少位。k == 0时直接返回head. 前面n - k 个不动，把后面k个移到前面，再把前面n - k个贴到后面。或者和rm n the node一样也是从后数k个，因此想到俩指针先后走解法。

Code

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        int n = 0;
        auto cur = head;
        while (cur != nullptr) {
            ++n;
            cur = cur->next;
        }
        if (!n) return head;
        k = k % n;
        if (k == 0) return head;
        cur = head;
        for (int i = 0; i < n - k - 1; ++i) {
            cur = cur->next;
        }
        auto new_head = cur->next;
        cur->next = nullptr;
        cur = new_head;
        while (cur->next != nullptr) {
            cur = cur->next;
        }
        cur->next = head;
        return new_head;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    private int getLen(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }


    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        int len = getLen(head);
        k = k % len;

        ListNode first = head, sec = head;
        for (int i = 0; i < k; i++) {
            first = first.next;
        }
        if (first == null) {
            return head;
        }

        while (first != null && first.next != null) {
            first = first.next;
            sec = sec.next;
        }
        ListNode last = first;
        last.next = head;
        head = sec.next;
        sec.next = null;

        return head;
    }
}

Analysis

做题耗时: 45 min

Errors:

1. 不知道k能大于len

2. 当first == null时应直接返回。

时间复杂度O(n). 空间O(1)