Linked Lists

The category contains all posts on linked lists. A child category to Data Structures

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

Merging two Sorted Singly Linked List

Introduction - Merging two Sorted Singly Linked List This question is mostly asked in interviews and hence I thought of writing few possible solutions to the same. I also asked the same question on stackoverflow.com. You can visit the link here Problem Statement You have two singly linked lists that are already sorted, you have to merge them and return the head of the new list without creating any new extra nodes. The returned list should be sorted as well The method signature is: [crayon-5b06dba1d8f48023105954/] Node class is below: [crayon-5b06dba1d8f50295452729/] Solution There c...
Read More