Question

Formatted question description: https://leetcode.ca/all/61.html

61	Rotate List

Given a 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


@tag-linkedlist

Algorithm

First traverse the original linked list to get the length n of the linked list, and then take the remainder of k to n, so that k must be less than n.

Use the fast and slow pointers to solve, the fast pointer first walks k steps, and then the two pointers go together, when the fast pointer reaches the end , The next position of the slow pointer is the head node of the new order, so that the linked list can be rotated.

Code

Java

public class Rotate_List {

	/**
	 * Definition for singly-linked list.
	 * public class ListNode {
	 *     int val;
	 *     ListNode next;
	 *     ListNode(int x) { val = x; }
	 * }
	 */
	public class Solution {
	    public ListNode rotateRight(ListNode head, int k) {

	        if (head == null) {
	            return head;
	        }

	        // k could be larger than list-length
	        int length = 0;
	        ListNode p = head;
	        while (p != null) {
	            length++;
	            p = p.next;
	        }

	        // avoid circle rotate
	        k = k % length;

	        if (k == 0) {
	            return head;
	        }

	        // two pointers, j is k behind i
	        ListNode i = head;
	        while (k > 0) {
	            i = i.next;
	            k--;
	        }
	        ListNode j = head;

	        while (i.next != null) { // i will stop at last node, j will stop at after-rotate end node

	            i = i.next;
	            j = j.next;
	        }

	        ListNode newHead = j.next; // @note: here, hidden assumption is "j.next != null” . eg: input: list=[1], k=0
	        j.next = null; // cut
	        i.next = head; // link

	        return newHead;
	    }

	}


    public class Solution_make_circle {

        public ListNode rotateRight(ListNode head, int n) {

            if (head == null || head.next == null || n == 0)
                return head;

            // compare list length with k, what if k is extremely large
            ListNode ptail = head;
            int count = 1;
            while (ptail.next != null) {
                count++;
                ptail = ptail.next;
            }

            int cutoff = count - (n % count);


            ptail.next = head; // @note: connect head tail, making it circular list

            for (int i = 0; i < cutoff; i++) {
                ptail = ptail.next;
            }

            ListNode newhead = ptail.next;
            ptail.next = null;
            return newhead;
        }
    }

}

// OJ: https://leetcode.com/problems/rotate-list/
// Time: O(N)
// Space: O(1)
class Solution {
    int getLength(ListNode *head) {
        int ans = 0;
        for (; head; head = head->next) ++ans;
        return ans;
    }
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) return nullptr;
        int len = getLength(head);
        k %= len;
        if (k == 0) return head;
        auto p = head, q = head;
        while (k--) q = q->next;
        while (q->next) p = p->next, q = q->next;
        auto ans = p->next;
        p->next = nullptr;
        q->next = head;
        return ans;
    }
};

# Definition for singly-linked list.
# class ListNode(object):
#     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 not head:
      return head
    l = 1
    p = head
    while p.next:
      l += 1
      p = p.next
    k = k % l
    if k == 0:
      return head
    k = l - k % l - 1
    pp = head
    print
    k
    while k > 0:
      pp = pp.next
      k -= 1
    newHead = pp.next
    pp.next = None
    p.next = head
    return newHead

61 - Rotate List

Question

Algorithm

Code

All Problems

All Solutions