给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL 

示例 2:

输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL 

题解

昨晚吃火锅吃撑了回来这道题，还算顺利~~ 链表的题目,其实就是在考指针交换,这个题目先让链表连成一个环，然后再切开就可以完成了。

python 版本

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def rotateRight(self, head, k): """ :type head: ListNode :type k: int :rtype: ListNode """ if head is None or head.next is None: return head # 链表的节点个数 count = 1 cur = head while cur.next: count += 1 cur = cur.next # 如果恰好走了一个环,就直接返回 k = k % count if k == 0: return head cur.next = head dummy = ListNode(-1) dummy.next = head prev = dummy # 需要走 count-k 个,然后把链表切断 for _ in range(count - k): prev = prev.next # 重新组成新的链表 cur = prev.next new_head = cur prev.next = None return new_head 

java 版本

public class Solution { public ListNode rotateRight(ListNode head, int k) { if (head == null || head.next == null) { return head; } int count = 1; ListNode cur = head; while (cur.next != null) { count++; cur = cur.next; } k = k % count; if (k == 0) { return head; } cur.next = head; ListNode dummy = new ListNode(-1); dummy.next = head; ListNode prev = dummy; for (int i = 0; i < count - k; i++) { prev = prev.next; } cur = prev.next; prev.next = null; return cur; } } 

热门阅读

• [ Leetcode ] 60. 第 k 个排列
• 技术文章汇总