reversing linked list

Linked List Batch Reversing

Introduction As I am writing this at 2 AM, this is going to be a small post but definitely an interesting one. This is mostly asked in interviews and is related to my previous post for Reversing a LinkedList. Understanding the problem statement Given a singly linked list L and a number k, we need to reverse each batch of k elements in the linked list. Here is a pictorial representation for the same. For the below input linked list and for k equals to 3, you can see the output linked list under it. Each of the triplets are reversed. Approach We need to use our reverse linked list func...
Read More

Adding numbers using Linked Lists

Introduction Adding numbers has always been fascinating and you may think it to be the easiest mathematical operation possible. But believe me many a times that becomes the toughest problem to solve. Let us discuss this in more detail. It is really easy to add two numbers stored in two memory locations. The ALU provides you the option to use the ADD feature and store it on the DATA bus. This is feasible when both the numbers can fit on the DATA bus one at a time. So, what about adding excessively large numbers, I know that the limit of BigInteger, Long, Double etc is too huge. But what if ...
Read More

Reversing a Singly Linked List

Introduction Many people have asked me to explain the dynamics of how the reversing of a singly linked list works, when we do not have the liberty of creating a new linked list, may be due to limitation of memory. The Idea behind Reversing a Singly Linked List The idea is to iterate through the complete linked list and maintain three pointers as listed below: Pointer to the head of un reversed list headOfUnReversedLL. Pointer to the head of reversed list headOfReversedLL. Pointer to the node to be reversed nodeToReverse. In each iteration we follow the below four steps: The h...
Read More