博客

题目：

http://oj.leetcode.com/problems/rotate-list/

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

.

题目翻译：

给定一个链表，向右旋转k个位置，其中k是非负的。

例如：

给定1->2->3->4->5->NULL和k = 2，

返回4->5->1->2->3->NULL。

分析：

把链表连成环，再在特定的位置断开。注意k可能大于链表的长度。

C++实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        if(head == NULL || k == 0)
    	{
    		return head;
    	}

    	int length = 1;
    	ListNode *node = head;
    	while(node->next != NULL) {
    		++length;
    		node = node->next;
    	}

    	node->next = head;

    	int m = k % length;

    	for(int i = 0; i < length - m; ++i)
    	{
    		node = node->next;
    	}

    	head = node->next;

    	node->next = NULL;

    	return head;
    }
};

Java实现：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if (head == null || n == 0) {
			return head;
		}

		int length = 1;
		ListNode node = head;
		while (node.next != null) {
			++length;
			node = node.next;
		}

		node.next = head;

		int m = n % length;

		for (int i = 0; i < length - m; ++i) {
			node = node.next;
		}

		head = node.next;

		node.next = null;

		return head;
    }
}

Python实现：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @param k, an integer
    # @return a ListNode
    def rotateRight(self, head, k):
        if head == None or k == 0:
            return head
        
        length = 1
        node = head
        while node.next != None:
            length += 1
            node = node.next
            
        m = k % length
        
        node.next = head
        
        for i in range(length - m):
            node = node.next
        
        head = node.next
        
        node.next = None
        
        return head

感谢阅读，欢迎评论！