Question

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

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

Constraints:

The number of nodes in the list is in the range [0, 500].
-100 <= Node.val <= 100
0 <= k <= 2 * 10⁹

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

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

}

############

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        int n = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) {
            ++n;
        }
        k %= n;
        if (k == 0) {
            return head;
        }
        ListNode slow = head, fast = head;
        while (k-- > 0) {
            fast = fast.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }

        ListNode start = slow.next;
        slow.next = null;
        fast.next = head;
        return start;
    }
}

// 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:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if k == 0 or head is None or head.next is None:
            return head
        n, cur = 0, head
        while cur:
            n, cur = n + 1, cur.next
        k %= n
        if k == 0:
            return head

        slow = fast = head
        for _ in range(k):
            fast = fast.next
        while fast.next:
            slow, fast = slow.next, fast.next

        start = slow.next
        slow.next = None
        fast.next = head
        return start

############

# 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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode RotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null)
        {
            return head;
        }
        var n = 0;
        for (ListNode cur = head; cur != null; cur = cur.next)
        {
            ++n;
        }
        k %= n;
        if (k == 0)
        {
            return head;
        }
        ListNode slow = head, fast = head;
        while (k-- > 0)
        {
            fast = fast.next;
        }
        while (fast.next != null)
        {
            slow = slow.next;
            fast = fast.next;
        }

        ListNode start = slow.next;
        slow.next = null;
        fast.next = head;
        return start;
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	cur := head
	n := 0
	for cur != nil {
		cur = cur.Next
		n++
	}
	k %= n
	if k == 0 {
		return head
	}
	fast, slow := head, head
	for i := 0; i < k; i++ {
		fast = fast.Next
	}
	for fast.Next != nil {
		fast = fast.Next
		slow = slow.Next
	}
	ans := slow.Next
	slow.Next = nil
	fast.Next = head
	return ans
}

61 - Rotate List

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions