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;
        }
    }

}

All Problems

All Solutions