Welcome to Subscribe On Youtube

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 * 109

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

All Problems

All Solutions