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
    
    

All Problems

All Solutions