61.md

【中规中矩】61. 旋转链表 （找到分割点，切断，旋转，重新连接）

解题思路

1.计算出链表的长度N 2. 往前走N-K步，找到分割点。将分割点的前一个节点的next置空。令newHead 为分割点节点 3. 走到当前剩余部分链表的结尾，令其next为原来的head，重新连接链表。 4. 返回newHead即可。

注意处理一些特殊情况，防止访问空指针即可。

代码

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !head->next) {
            return head;
        }

        auto listLen = getListLen(head);
        k = k % listLen;
        if (k == 0) {
            return head;
        }
        ListNode* pre = nullptr;
        auto p = head;
        for (int i = 0; i < listLen - k; i++) {
            pre = p;
            p = p->next;
        }

        pre->next = nullptr;
        auto newHead = p;
        while (p && p->next) {
            p = p->next;
        }
        if (p) {
            p->next = head;
        }

        return newHead;
    }

private:
    int getListLen(ListNode* head) {
        int count = 0;
        while (head) {
            head = head->next;
            count++;
        }

        return count;
    }
};

     

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if (not head or not head.next) :
            return head

        listLen = self.__getListLen(head)
        k = k % listLen
        if (k == 0) :
            return head

        pre = None
        p = head
        for i in range(0, listLen - k) :
            pre = p
            p = p.next
        pre.next = None
        newHead = p
        while (p and p.next) :
            p = p.next
        if (p) :
            p.next = head

        return newHead

    def __getListLen(self, head: ListNode) :
        count = 0
        while (head) :
            head = head.next
            count += 1

        return count

点我赞赏作者

github 题解