Rotate List

Fill out the following sections:

Define the Interface Input: head, k (integer) Output: head

How is the number of nodes in the linked list related to value of k. The highest value for the length of the linked list is 500, but k can be 501 Rotating 501 times is the same as rotating just once Can we avoid doing unnecessary work (rotation) What is the minimum rotation we need to perform. Figure out how many nodes is in the linked list Compute k % n (modular arithmetic) 501 % 500 = 1

Identify the Invariants The values of the nodes will not change The number of nodes will not change

Identify the constraints

no of nodes [0, 500]
k [0, 2*10^9]

Search the Problem Space

Classify the Problem

Analyze the Examples

Solve the Problem by Hand If I rotate the linked list by the same number of times as the number of nodes in the linked list

How do we express this in code?

Traverse the linked list and when the pointer reaches the last node Last node’s next pointer must point to head We need more than one pointer because, I need to set the node before the last node to be f.next = l.next (make the new tail) l.next = head ()

Go to the second last node Save the last node Assign second_last.next to null Assign last_node.next = head Assign head = last_node

Iteration or Recursion Iteration - Figure out the value of k (modulo) - Rotate k number of times - Terminating condition is the value of k
- Return the head of the rotated linked list

If we have 0 or 1 node, there is nothing to rotate Just return the head. If k = 0, no rotation required, return the head

Describe the Pattern

Brute Force Approach

Analyze Time and Space Complexity

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} head
# @param {Integer} k
# @return {ListNode}
=begin
   Go to the second last node
   Save the last node
   Assign second_last.next to null
   Assign last_node.next = head
   Assign head = last_node
=end

def rotate_right(head, k)
   if head.nil? || head.next.nil?
       return head
   end
   n = 0
   current = head

   while current
      n += 1
      current = current.next
   end
    
   k = k % n
   current = head
   last = nil

   while k != 0
     while current.next && current.next.next
       current = current.next
     end
     last = current.next
     current.next = nil
     last.next = head if last
     head = last
     current = head
     k -= 1
   end

   return head
end

Fill out the following sections:

Define the Interface Input: head, k (integer) Output: head

Identify the Invariants The values of the nodes will not change The number of nodes will not change

Identify the constraints

no of nodes [0, 500]
k [0, 2*10^9]

Search the Problem Space

Classify the Problem

Analyze the Examples

Solve the Problem by Hand If I rotate the linked list by the same number of times as the number of nodes in the linked list

How do we express this in code?

Go to the second last node Save the last node Assign second_last.next to null Assign last_node.next = head Assign head = last_node

Iteration or Recursion Iteration - Figure out the value of k (modulo) - Rotate k number of times - Terminating condition is the value of k
- Return the head of the rotated linked list

If we have 0 or 1 node, there is nothing to rotate Just return the head. If k = 0, no rotation required, return the head

Describe the Pattern

Brute Force Approach

Analyze Time and Space Complexity

Time: O(N) Space: O(1)

Next Problems

Rotate Array Split Linked List in Parts

Outline the Solution

Key Takeaways

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} head
# @param {Integer} k
# @return {ListNode}
=begin
   Go to the second last node
   Save the last node
   Assign second_last.next to null
   Assign last_node.next = head
   Assign head = last_node
=end

def rotate_right(head, k)
   if head.nil? || head.next.nil?
       return head
   end
   n = 0
   current = head
    
   while current
      n += 1
      current = current.next
   end
    
   k = k % n
   current = head
   last = nil
    
   while k != 0
     while current.next && current.next.next
       current = current.next
     end
     last = current.next
     current.next = nil
     last.next = head 
     head = last
     current = head
     k -= 1
   end
    
   return head
end

To rotate the linked list to the right by \( k \) places, you can follow these steps:

1. **Find the Length of the List:** First, iterate through the linked list to find its length.

2. **Determine the Effective Rotations:** Since rotating the list by its length doesn't change it, you need to find the effective number of rotations by taking the remainder of \( k \) divided by the length of the list.

3. **Find the Rotation Point:** Then, iterate through the list again until you reach the point where the rotation should start.

4. **Rotate the List:** Finally, update the pointers to perform the rotation.

Here's the code that implements these steps:

```python
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or k == 0:
            return head

        # Step 1: Find the length of the list
        length = 1
        tail = head
        while tail.next:
            tail = tail.next
            length += 1

        # Step 2: Determine the effective rotations
        k = k % length
        
        if k == 0:
            return head

        # Step 3: Find the rotation point
        prev = None
        current = head
        for _ in range(length - k):
            prev = current
            current = current.next

        # Step 4: Rotate the list
        prev.next = None
        tail.next = head
        head = current
        
        return head

This code first calculates the length of the linked list and then finds the effective rotations. After identifying the rotation point, it updates the pointers to rotate the list to the right by ( k ) places.

The time complexity is ( O(N) ), where ( N ) is the number of nodes in the linked list, as we have two iterations through the list. The space complexity is ( O(1) ), as we only use a constant amount of extra space.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        
        if not head:
            return None
        
        lastElement = head
        length = 1

        while ( lastElement.next ):
            lastElement = lastElement.next
            length += 1

        k = k % length
            
        lastElement.next = head
        
        tempNode = head
        for _ in range( length - k - 1 ):
            tempNode = tempNode.next
        
        answer = tempNode.next
        tempNode.next = None
        
        return answer

Language Agnostic Coding Drills

Understanding Data Structures: The first step in understanding this code is to understand data structures, specifically the queue and list data structures. Understand how these data structures work, how to add and remove elements, and how they can be used to store data.
- Drill: Use any language to implement a queue data structure and perform basic operations like enqueue (inserting an element at the end) and dequeue (removing an element from the front).
Condition Checking: The code uses a lot of condition checking (if statements) to decide what to do. This is a fundamental part of most programming languages.
- Drill: Write a function that takes an input, checks if it meets a certain condition, and returns different results based on that condition.
Loops: Loops are used to iterate over elements in a list or queue, or to keep a block of code running as long as a certain condition is true.
- Drill: Write a function that uses a loop to process or generate a sequence of values.
Functions/Methods: Functions or methods are blocks of reusable code that perform a certain task. Understanding how to define and use functions/methods is crucial.
- Drill: Define a function that takes in parameters, performs a calculation or operation, and returns a result.
Recursion: The given code uses recursion, which is the concept where a function calls itself in its definition. Recursive solutions are common for problems involving trees or graphs.
- Drill: Implement a simple recursive function, such as one that calculates the factorial of a number.
Tree Data Structure: The code is written for a tree data structure. Understanding trees is necessary to follow along. This includes understanding terms like root, node, child, etc.
- Drill: Implement a simple binary tree data structure and write functions to add nodes and traverse the tree.
Graph Traversal Algorithms (DFS, BFS): The code seems to be using a Breadth-first Search (BFS) traversal algorithm to navigate through the tree. Understanding how these algorithms work is crucial.
- Drill: Implement a BFS and DFS traversal on a tree or graph.
Complexity Analysis: Analyze and understand the time and space complexity of your code.
- Drill: Practice calculating the time and space complexity of various pieces of code.

Each of these drills isolates a particular concept, allowing you to focus on understanding and mastering that concept. Once you’re comfortable with these concepts, you can then combine them as demonstrated in the initial code sample.

Targeted Drills in Python

Understanding Data Structures (Queue)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Queue:
    def __init__(self):
        self.queue = []

    # Add an element
    def enqueue(self, item):
        self.queue.append(item)

    # Remove an element
    def dequeue(self):
        if len(self.queue) < 1:
            return None
        return self.queue.pop(0)

Condition Checking

1
2
3
4
5
def check_number(n):
    if n > 10:
        return 'Greater than 10'
    else:
        return 'Not greater than 10'

Loops

1
2
3
def print_numbers(n):
    for i in range(n):
        print(i)

Functions/Methods

1
2
def calculate_area(length, breadth):
    return length * breadth

Recursion

1
2
3
4
5
def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

Tree Data Structure

1
2
3
4
5
class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

Graph Traversal Algorithms (BFS)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
from collections import deque

def bfs(graph, root):
    visited, queue = set(), deque([root])
    visited.add(root)
    while queue:
        vertex = queue.popleft()
        print(str(vertex) + " ", end="")
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

Complexity Analysis This is more of a theoretical concept and understanding, but you can practice it by implementing different algorithms and analyzing their time and space complexity. For instance, you can check the time complexity of a simple sorting algorithm:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
import time
def bubble_sort(nums):
    for i in range(len(nums)):
        for j in range(len(nums) - 1):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]

nums = [5, 2, 1, 8, 4]
start_time = time.time()
bubble_sort(nums)
end_time = time.time()
print("Time taken for bubble sort:", end_time - start_time)

This script will print out the time taken for bubble sort, which has a time complexity of O(n^2).