[Interview Question] Reverse A Linked List - 3 Difficulties (on Leetcode)

To watch the youtube video going over this topic, click here.

Introduction

Linked Lists are a fundamental data structure, and they're often asked about in interview questions. Being able to work with multiple levels of a linked list teaches you how to work with all categories of linked list problems.

In this blogpost we'll go through three layers of reversing a linked list, all of which increase in difficulty, but are related to the same base algorithm. (All of these questions are problems on Leetcode.)

The problems we'll review are:

1. Reverse a(n entire) linked list
2. Reverse a linked list from node m to node n
3. Reverse a linked list in k groups

[Easy] Reverse A Linked List

Given the head of a singly linked list, reverse it. (Leetcode Problem.)

Reversing a linked list.

---

Solution (Iterative Approach)

We want to iterate through the linked list and change each node's next pointer to point to the previous node in the list.

To do this, we need too maintain two extra pointers while traversing the list, one that points to the previous node and one that points to the current node we're updating.

The steps involved in reversing a linked list. For each node, we make the "next" pointer point to the previous node in the list. We can safely do this because we maintain pointers to the two sections of the linked lists (since this splits the list).

​​Here's some C++ Code that does the iterative approach.

The time complexity is O(N) because we visit each node in the list once.
The space complexity is O(1) because the only extra data we have is three pointers.

[Medium] Reverse A Linked List From Node m to Node n

Given the head of a singly linked list, reverse nodes m to n. (Problem on Leetcode.)

Reversing a linked list from node m to node n.

---

Solution (Iterative Approach)

The "reversing" part is going to be the same algorithm as the base problem. The difference is, this time we have to start/stop reversing at specific nodes, and we're left with some disconnected sublists that we need to rejoin. To do this, we just need to maintain two extra pointers, one pointer to the node before the reversed chain, and one pointer to the end of the reversed chain.

The algorithm is as follows:

1. Setup the usual prev and curr pointers.
2. Traverse the list until curr is pointing to node m.
3. Create two new pointers, beforeReverse (equal to prev) and lastInReverse (equal to curr).
4. Start doing the reversal. (Same as the previous algorithm.) Stop after we reverse node n.
5. Fix any connections between the beforeChain, reverseChain, and afterChain.

Here's a diagram of that algorithm in action:

The steps invollved in reverse a linked list from node m to n. We maintain two new pointers (compared to the easy problem), do the normal reverse, and use our extra pointers to reconnect the lists.

Here's C++ code that implements this algorithm:

The time complexity is O(N) because we visit each node in the list once.
The space complexity is O(1) because the only extra data we have is three pointers.

[Hard] Reverse A Linked List In k Groups

Given the head of a singly linked list, reverse groups of k-nodes at a time. If there aren't k nodes left for a group, then don't reverse them.  (Problem on Leetcode.)

Reverse a linked list in k groups.

---

Solution (Iterative)

The solution to this problem builds on the previous two problems: we still use the "change next pointer to point to the previous node" reverse technique from the easy problem, and we still worry about reconnecting chains after the reversal, like the medium problem.

The difference is, this time we'll continuously reverse, starting from the head of the linked list, until we run out of k-length chains to reverse. The one thing we have to keep in mind is updating the prev pointer after each reversal chain.

The steps we take to reverse a linked list in k groups. The basic steps are: 1) do the reversal on the group (of size k). 2) Reconnect the lists. 3) Adjust the pointers for the next group.

Here's C++ code that implements the algorithm:

The time complexity is O(N) because we visit each node in the list twice.
The space complexity is O(1) because the only extra data we have is a few pointers and integers.

Alternative Solutions

We should make note that the way we solved these problems were all through an iterative algorithm. There are three other types of algorithms possible, but they're all not ideal:

1. Stack - You could push the nodes being reversed onto a stack, but that solution requires extra space and is more complex.
2. Recursion - We could try to recursively solve these problems, but that's wayyy more complicated and also requires extra space.
3. Swap Data Within Nodes - It's possible to swap the data in the nodes instead of switching pointers, but since we're working with singly listed lists this isn't an efficient solution, and it's not always ideal to modify the data like that.

​Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels. 

Twitter: @srcmake
Discord: srcmake#3644
Youtube: srcmake
Twitch: www.twitch.tv/srcmake
​Github: srcmake