考察的知识点:与链表有关的题基本都是插入,删除,交换顺序等,解决这些问题通常将链表的指针进行修改。
问题分析:将链表向右移动 k 个位置,头结点就变成原来链表的倒数第k个结点,所以可以用快慢指针,找出倒数第k个位置的结点,然后将链表重新连接起来。倒数第k个位置结点的前一个结点的next需要修改为空,所以直接找倒数第k+1个结点。
本题解析所用的编程语言:c++
ListNode* rotateLeft(ListNode* head, int k) { //k可能比链表的长度大,所以先将k取余 ListNode* cur = head; int length = 0; while (cur) { ++length; cur = cur->next; } k %= length; //快慢指针寻找第k+1个结点的位置 ListNode* fast = head, * slow = head; while (k--) { fast = fast->next; } while (fast->next) { fast = fast->next; slow = slow->next; } //将链表重新进行连接 fast->next = head; head = slow->next; slow->next = nullptr; return head; }