Shift linked list problem

I. Introduction

In the previous part, I introduced you to the classic algorithm question - Reverse linked list. Now I will introduce another classic question about linked lists, which is shift linked list. In this article, I will give 2 ways to solve the problem and analyze the space and time complexity of each way. I will assume that you already know about the linked list data structure when reading this article. If not, you can read the document "Basic linked list" of Stanford University, USA here.

II. Topic

Write a function that takes the head of a Singly Linked List and a number k, shifts the list in place k positions, and returns the new head after shifting. The number k can be positive or negative; this means you have to handle two cases: shifting the linked list forward and backward.

Input 1:

Output 1:

Input 2:

Output 2:

In the following sections, I will give two ways to solve this problem.

III. Solution 1: Connect the linked list into a loop

To be able to shift linked list to create a new linked list, we will join linked list into a loop linked list then find new head and break the loop at new head to create new linked list. Below is the description of my solution:

 

The detailed steps are as follows:

Use the two pointers approach: One pointer points to the head, the other pointer moves to the tail of the linked list. Then attach tail.next = head to create a loop if k > 0: the new head will be the (k % length)th node from the tail. For example, if the length of the linked list is 6, k = 2, the new head will be the 2nd node from the tail; if k = 8, the new head will also be the 2nd node from the tail. If k < 0: the new head will be the ( |k| % length )th node from the head. For example, if the length of the linked list is 6, k = -2, the new head will be the 2nd node from the head. We break the loop into a normal linked list by attaching new_tail.next = None

Here is my solution to this approach:

Space and time complexity analysis

Note: n is the number of nodes of the input linked list

Space complexity is O(1):

Since the entire algorithm processes directly on the input linked list, the space complexity is constant - O(1)

Time complexity is O(n):

Time complexity for pointer to reach tail node is O(n)

Time complexity to join linked list is O(1)

Time complexity to find new head in worst case is O(n)

Time complexity to break linked list loop is O(1)

Therefore, the total time complexity is O(1)

Approach 2: use list as intermediary

Similar to linked list, we can solve the linked list problem through lists and then reconstruct a linked list. Here is my description:

 

The detailed steps are as follows:

We convert from linked list to list Based on the shift properties mentioned in approach 1, we calculate magic number = k % length Then, perform shift on this list with the format list[-magic:] + list[:-magic] Rebuild the linked list on the shifted list

My solution to this approach:

Space and time complexity analysis:

Space complexity is O(n):

Space complexity to convert from linked list to list is O(n) Space complexity to construct linked list from new list is O(n) Therefore, total space complexity is O(n)

Time complexity is O(n):

Time complexity to convert from linked list to list is O(n)

Time complexity to build linked list from new list is O(n)

Therefore, the total time complexity is O(n)

III. Conclusion

The above two solutions are not all the ways to shift a linked list but are two quite typical ways for this classic problem. Hopefully this blog post can help you in some way. If you find the blog post interesting, please share it so that more people know about it. And look forward to more of my blog posts on the topic of Data Structure & Algorithm on TipsMake's tech blog!