Description
Given a linked list, rotate the list to the right by k places, where k is non-negative.
Example 1:
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
Example 2:
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
描述
给定链表，将列表向右旋转k个位置，其中k为非负数。
思路
- 这道题是给定一个链表，让后给定一个非负整数k，要求将链表的最后一个元素放到链表的首位，执行k次.
- 这道题目相对比较简单，我们首先对k做一次预处理
- 我们获取链表的长度length，令k = k % length：比如如果链表有3个元素，k=7和k=1的效果是一样的
- 然后我们获取倒数第k+1的元素，获取其指向的下一个元素的索引，赋值给res，然后将其置为None.
- 最后再将原来的末尾的索引指向头部，返回res即可
class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def rotateRight(self, head, k): """ :type head: ListNode :type k: int :rtype: ListNode """ # 如果head指向空或者k==0则直接返回 if not head or k == 0: return head count, before, last = 1, head, head # 统计一共有多少个元素 while before.next: count += 1 before = before.next # before重新回到起始位置 before = head # 对k进行求模运算，避免重复搬运 k = k % count # 如果k求模运算结果为0，则仍然直接返回 if k == 0: return head # last指向编号为k的元素 for _ in range(k): last = last.next # 找到倒数第k+1个元素 while last and last.next: last = last.next before = before.next # 将倒数第k+1个元素指向元素的引用赋值给res，改变倒数第k+1个元素的指向为None，将原本的last.next指向头节点 res = before.next before.next = None last.next = head return res
源代码文件在这里.
