

Hasuer's Studio.

Hasuer's Studio.

6. Pattern In-place Reversal of a LinkedList



6. Pattern In-place Reversal of a LinkedList

Grokking Interview Pattern Interview

Word count: 2.5kReading time: 15 min

 2024/05/06   Share

• 
• 
• 
• 
• 

Introduction

In a lot of problems, we are asked to reverse the links between a set of nodes of a LinkedList. Often, the constraint is that we need to do this in-place, i.e., using the existing node objects and without using extra memory.

In-place Reversal of a LinkedList pattern describes an efficient way to solve the above problem. In the following chapters, we will solve a bunch of problems using this pattern.

Let’s jump on to our first problem to understand this pattern.

Reverse a LinkedList (easy)

206. Reverse Linked List Design Gurus Educative.io

Problem Statement

Given the head of a Singly LinkedList, reverse the LinkedList. Write a function to return the new head of the reversed LinkedList.

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

Solution

To reverse a LinkedList, we need to reverse one node at a time. We will start with a variable current which will initially point to the head of the LinkedList and a variable previous which will point to the previous node that we have processed; initially previous will point to null.

In a stepwise manner, we will reverse the current node by pointing it to the previous before moving on to the next node. Also, we will update the previous to always point to the previous node that we have processed. Here is the visual representation of our algorithm:

Code

Here is what our algorithm will look like:

# class Node:
#     def __init__(self, value, next=None):
#         self.val = value
#         self.next = next

class Solution:
    def reverse(self, head):
        previous, current, next = None, head, None
        while current is not None:
            next = current.next  # temporarily store the next node
            current.next = previous  # reverse the current node
            # before we move to the next node, point previous to the current node
            previous = current
            current = next  # move on the next node
        return previous


def print_list(head):
    temp = head
    while temp is not None:
        print(temp.val, end=" ")  # Use temp.val to access the value
        temp = temp.next
    print()


def main():
    sol = Solution()
    head = Node(2)
    head.next = Node(4)
    head.next.next = Node(6)
    head.next.next.next = Node(8)
    head.next.next.next.next = Node(10)

    print("Nodes of original LinkedList are: ", end='')
    print_list(head)
    result = sol.reverse(head)
    print("Nodes of reversed LinkedList are: ", end='')
    print_list(result)


if __name__ == "__main__":
    main()

Time complexity

The time complexity of our algorithm will be O(N) where ‘N’ is the total number of nodes in the LinkedList.

Space complexity

We only used constant space, therefore, the space complexity of our algorithm is O(1).

*Reverse a Sub-list (medium)

Top Interview 150 | 92. Reverse Linked List II Design Gurus Educative.io

Problem Statement

Given the head of a LinkedList and two positions ‘p’ and ‘q’, reverse the LinkedList from position ‘p’ to ‘q’.

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

Solution

The problem follows the In-place Reversal of a LinkedList pattern. We can use a similar approach as discussed in Reverse a LinkedList. Here are the steps we need to follow:

1. Skip the first p-1 nodes, to reach the node at position p.
2. Remember the node at position p-1 to be used later to connect with the reversed sub-list.
3. Next, reverse the nodes from p to q using the same approach discussed in Reverse a LinkedList.
4. Connect the p-1 and q+1 nodes to the reversed sub-list.
5. 思路和我的是一样的，比较好奇他是怎么解决P == 1的情况的

Code

Here is what our algorithm will look like:

class Node:
    def __init__(self, value, next=None):
        self.val = value
        self.next = next

class Solution:
    def reverse(self, head, p, q):
        if p == q:
            return head

        # after skipping 'p-1' nodes, current will point to 'p'th node
        current, previous = head, None
        i = 0
        while current is not None and i < p - 1:
            previous = current
            current = current.next
            i += 1

        # we are interested in three parts of the LinkedList, the part before index 'p',
        # the part between 'p' and 'q', and the part after index 'q'
        last_node_of_first_part = previous
        # after reversing the LinkedList 'current' will become the last node of the sub-list
        last_node_of_sub_list = current # reverse之后的last_node
        next = None  # will be used to temporarily store the next node

        i = 0
        # reverse nodes between 'p' and 'q'
        while current is not None and i < q - p + 1:
            next = current.next
            current.next = previous
            previous = current
            current = next
            i += 1

        # connect with the first part
        if last_node_of_first_part is not None:
            # 'previous' is now the first node of the sub-list
            last_node_of_first_part.next = previous
        # this means p == 1 i.e., we are changing the first node (head) of the LinkedList
        else:
            head = previous

        # connect with the last part
        last_node_of_sub_list.next = current
        return head


def print_list(head):
    temp = head
    while temp is not None:
        print(temp.val, end=" ")
        temp = temp.next
    print()


def main():
    sol = Solution()
    head = Node(1)
    head.next = Node(2)
    head.next.next = Node(3)
    head.next.next.next = Node(4)
    head.next.next.next.next = Node(5)

    print("Nodes of original LinkedList are: ", end='')
    print_list(head)
    result = sol.reverse(head, 2, 4)
    print("Nodes of reversed LinkedList are: ", end='')
    print_list(result)


if __name__ == "__main__":
    main()

Time complexity

The time complexity of our algorithm will be O(N) where ‘N’ is the total number of nodes in the LinkedList.

Space complexity

We only used constant space, therefore, the space complexity of our algorithm is O(1).

---

Similar Questions

Problem 1: Reverse the first ‘k’ elements of a given LinkedList.

Solution: This problem can be easily converted to our parent problem; to reverse the first ‘k’ nodes of the list, we need to pass p=1 and q=k.

Problem 2: Given a LinkedList with ‘n’ nodes, reverse it based on its size in the following way:

1. If ‘n’ is even, reverse the list in a group of n/2 nodes.
2. If n is odd, keep the middle node as it is, reverse the first ‘n/2’ nodes and reverse the last ‘n/2’ nodes.

Solution: When ‘n’ is even we can perform the following steps:

1. Reverse first ‘n/2’ nodes: head = reverse(head, 1, n/2)
2. Reverse last ‘n/2’ nodes: head = reverse(head, n/2 + 1, n)

When ‘n’ is odd, our algorithm will look like:

1. head = reverse(head, 1, n/2)
2. head = reverse(head, n/2 + 2, n)

Please note the function call in the second step. We’re skipping two elements as we will be skipping the middle element.

*Reverse every K-element Sub-list (medium)

Similar |Top Interview 150 | 25. Reverse Nodes in k-Group Design Gurus Educative.io

Problem Statement

Given the head of a LinkedList and a number ‘k’, reverse every ‘k’ sized sub-list starting from the head.

If, in the end, you are left with a sub-list with less than ‘k’ elements, reverse it too.

Constraints:

• The number of nodes in the list is n.
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

Solution

The problem follows the In-place Reversal of a LinkedList pattern and is quite similar to Reverse a Sub-list. The only difference is that we have to reverse all the sub-lists. We can use the same approach, starting with the first sub-list (i.e. p=1, q=k) and keep reversing all the sublists of size ‘k’.

Code

Most of the code is the same as Reverse a Sub-list; only the highlighted lines have a majority of the changes:

# class Node:
#  def __init__(self, val, next=None):
#    self.val = val
#    self.next = next

class Solution:
    def reverse(self, head, k):
        if k <= 1 or head is None:
            return head

        current, previous = head, None
        while current is not None: # break if we've reached the end of the list
            last_node_of_previous_part = previous
            # after reversing the LinkedList 'current' will become the last node of the sub-list
            last_node_of_sub_list = current
            next = None  # will be used to temporarily store the next node
            i = 0
            while current is not None and i < k:  # reverse 'k' nodes
                next = current.next
                current.next = previous
                previous = current
                current = next
                i += 1

            # connect with the previous part
            if last_node_of_previous_part is not None:
                last_node_of_previous_part.next = previous
            else:
                head = previous

            # connect with the next part
            last_node_of_sub_list.next = current

            previous = last_node_of_sub_list
        return head


def print_list(head):
    temp = head
    while temp is not None:
        print(temp.val, end=" ")
        temp = temp.next
    print()


def main():
    sol = Solution()
    head = Node(1)
    head.next = Node(2)
    head.next.next = Node(3)
    head.next.next.next = Node(4)
    head.next.next.next.next = Node(5)
    head.next.next.next.next.next = Node(6)
    head.next.next.next.next.next.next = Node(7)
    head.next.next.next.next.next.next.next = Node(8)

    print("Nodes of original LinkedList are: ", end='')
    print_list(head)

    result = sol.reverse(head, 3)
    print("Nodes of reversed LinkedList are: ", end='')
    print_list(result)


main()

Time complexity

The time complexity of our algorithm will be O(N) where ‘N’ is the total number of nodes in the LinkedList.

Space complexity

We only used constant space, therefore, the space complexity of our algorithm is O(1).

*Problem Challenge 1

Design Gurus Educative.io

Reverse alternating K-element Sub-list (medium)

Given the head of a LinkedList and a number ‘k’, reverse every alternating ‘k’ sized sub-list starting from the head.

If, in the end, you are left with a sub-list with less than ‘k’ elements, reverse it too.

Constraints:

• The number of nodes in the list is n.
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

Solution

The problem follows the In-place Reversal of a LinkedList pattern and is quite similar to Reverse every K-element Sub-list. The only difference is that we have to skip ‘k’ alternating elements. We can follow a similar approach, and in each iteration after reversing ‘k’ elements, we will skip the next ‘k’ elements.

Code

Most of the code is the same as Reverse every K-element Sub-list; only the highlighted lines have a majority of the changes:

# class Node:
#  def __init__(self, val, next=None):
#    self.val = val
#    self.next = next

class Solution:
    def reverse(self, head, k):
        if k <= 1 or head is None:
            return head

        current, previous = head, None
        while current is not None:  # break if we've reached the end of the list
            last_node_of_previous_part = previous
            # after reversing the LinkedList 'current' will become the last node of the sub-list
            last_node_of_sub_list = current
            next = None  # will be used to temporarily store the next node

            # reverse 'k' nodes
            i = 0
            while current is not None and i < k:
                next = current.next
                current.next = previous
                previous = current
                current = next
                i += 1

            # connect with the previous part
            if last_node_of_previous_part is not None:
                last_node_of_previous_part.next = previous
            else:
                head = previous

            # connect with the next part
            last_node_of_sub_list.next = current

            # skip 'k' nodes
            i = 0
            while current is not None and i < k:
                previous = current
                current = current.next
                i += 1

        return head


def print_list(self):
    temp = self
    while temp is not None:
        print(temp.val, end=" ")
        temp = temp.next
    print()


def main():
    sol = Solution()
    head = Node(1)
    head.next = Node(2)
    head.next.next = Node(3)
    head.next.next.next = Node(4)
    head.next.next.next.next = Node(5)
    head.next.next.next.next.next = Node(6)
    head.next.next.next.next.next.next = Node(7)
    head.next.next.next.next.next.next.next = Node(8)

    print("Nodes of original LinkedList are: ", end='')
    print_list(head)
    result = sol.reverse(head, 2)
    print("Nodes of reversed LinkedList are: ", end='')
    print_list(result)


main()

Time complexity

The time complexity of our algorithm will be O(N) where ‘N’ is the total number of nodes in the LinkedList.

Space complexity

We only used constant space, therefore, the space complexity of our algorithm is O(1).

Problem Challenge 2

Top Interview 150 | 61. Rotate List Design Gurus Educative.io

Rotate a LinkedList (medium)

Given the head of a Singly LinkedList and a number ‘k’, rotate the LinkedList to the right by ‘k’ nodes.

Solution

Another way of defining the rotation is to take the sub-list of ‘k’ ending nodes of the LinkedList and connect them to the beginning. Other than that we have to do three more things:

1. Connect the last node of the LinkedList to the head, because the list will have a different tail after the rotation.
2. The new head of the LinkedList will be the node at the beginning of the sublist.
3. The node right before the start of sub-list will be the new tail of the rotated LinkedList.

Code

Here is what our algorithm will look like:

# class Node:
#  def __init__(self, Val, next=None):
#    self.val = Val
#    self.next = next

class Solution:
    def rotate(self, head, rotations):
        if head is None or head.next is None or rotations <= 0:
            return head

        # find the length and the last node of the list
        last_node = head
        list_length = 1
        while last_node.next is not None:
            last_node = last_node.next
            list_length += 1

        last_node.next = head  # connect the last node with the head to make it a circular list
        rotations %= list_length  # no need to do rotations more than the length of the list
        skip_length = list_length - rotations
        last_node_of_rotated_list = head
        # 找尾巴，这样下一个就是new_head
        for i in range(skip_length - 1):
            last_node_of_rotated_list = last_node_of_rotated_list.next

        # 'last_node_of_rotated_list.next' is pointing to the sub-list of 'k' ending nodes
        head = last_node_of_rotated_list.next
        last_node_of_rotated_list.next = None
        return head


def print_list(head):
    temp = head
    while temp is not None:
        print(temp.val, end=" ")
        temp = temp.next
    print()


def main():
    sol = Solution()
    head = Node(1)
    head.next = Node(2)
    head.next.next = Node(3)
    head.next.next.next = Node(4)
    head.next.next.next.next = Node(5)
    head.next.next.next.next.next = Node(6)

    print("Nodes of original LinkedList are: ", end='')
    print_list(head)
    result = sol.rotate(head, 3)
    print("Nodes of rotated LinkedList are: ", end='')
    print_list(result)


main()

Time complexity

The time complexity of our algorithm will be O(N) where ‘N’ is the total number of nodes in the LinkedList.

Space complexity

We only used constant space, therefore, the space complexity of our algorithm is O(1).

Author：Hasuer

Link：https://hasuer.github.io/6-pattern-in-place-reversal-of-a-linkedlist/index.html

Publish date：May 6th 2024, 3:35:04 pm

Update date：May 28th 2024, 11:27:47 am

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

• Next Post
  7. Pattern Stack
• Previous Post
  5. Pattern Cyclic Sort

Powered by Hexotheme Archer

PV: :)

CATALOG

1. 1. Introduction
2. 2. Reverse a LinkedList (easy)
   1. 2.1. Problem Statement
   2. 2.2. Solution
   3. 2.3. Code
      1. 2.3.1. Time complexity
      2. 2.3.2. Space complexity
3. 3. *Reverse a Sub-list (medium)
   1. 3.1. Problem Statement
   2. 3.2. Solution
   3. 3.3. Code
      1. 3.3.1. Time complexity
      2. 3.3.2. Space complexity
   4. 3.4. Similar Questions
4. 4. *Reverse every K-element Sub-list (medium)
   1. 4.1. Problem Statement
   2. 4.2. Solution
   3. 4.3. Code
      1. 4.3.1. Time complexity
      2. 4.3.2. Space complexity
5. 5. *Problem Challenge 1
   1. 5.1. Reverse alternating K-element Sub-list (medium)
   2. 5.2. Solution
   3. 5.3. Code
      1. 5.3.1. Time complexity
      2. 5.3.2. Space complexity
6. 6. Problem Challenge 2
   1. 6.1. Rotate a LinkedList (medium)
   2. 6.2. Solution
   3. 6.3. Code
      1. 6.3.1. Time complexity
      2. 6.3.2. Space complexity

• Archive
• Tag
• Cate

Total : 41

2024

• 06/02 34. Conclusions
• 06/02 33. Test Your Knowledge (Hard)
• 06/01 32. Test Your Knowledge (Medium)
• 05/31 31. Test Your Knowledge (Easy).md
• 05/30 30. Revision
• 05/29 29. Miscellaneous
• 05/28 28. Pattern Multi-thread
• 05/27 27. Pattern Prefix Sum
• 05/26 26. Pattern Ordered Set
• 05/25 25. Pattern Union Find
• 05/24 24. Pattern Topological Sort (Graph)
• 05/23 23. Pattern Trie
• 05/22 22. Pattern Backtracking
• 05/21 21. Pattern 01 Knapsack (Dynamic Programming)
• 05/20 20. Pattern Greedy Algorithms
• 05/19 19. Pattern K-way merge
• 05/18 18. Pattern Top 'K' Elements
• 05/17 17. Pattern Bitwise XOR
• 05/16 16. Pattern Modified Binary Search
• 05/15 15. Pattern Subsets
• 05/14 14. Pattern Two Heaps
• 05/13 13. Pattern Island (Matrix traversal)
• 05/12 12. Pattern Graphs
• 05/11 11. Pattern Tree Depth First Search
• 05/10 10. Pattern Tree Breadth First Search
• 05/09 9. Pattern Hash Maps
• 05/08 8. Pattern Monotonic Stack
• 05/07 7. Pattern Stack
• 05/06 6. Pattern In-place Reversal of a LinkedList
• 05/05 5. Pattern Cyclic Sort
• 05/04 4. Pattern Merge Intervals
• 05/03 3. Pattern Sliding Window
• 05/02 2. Pattern Fast_Slow pointers
• 05/01 1. Pattern Two Pointers
• 04/30 0.Introduction

2022

• 06/12 Ubuntu20.04安装配置MySQL8(详细)
• 02/25 Axios学习笔记
• 02/23 Promise学习笔记
• 02/23 Nginx学习笔记
• 02/23 AJAX学习笔记

2021

• 07/07 Git学习笔记

 Interview



缺失模块，请参考主题文档进行安装配置：https://github.com/fi3ework/hexo-theme-archer#%E5%AE%89%E8%A3%85%E4%B8%BB%E9%A2%98

 技术笔记  Grokking-Interview-Pattern

