Leetcode Solutions #2

1. Sort List

The Problem

First read the description of problem:

Given the head of a linked list, return the list after sorting it in ascending order.

So here, basically we have to return the linked list after sorting it in ascending order.

Approach

There are a lot of ways to solve this question but one of the easiest and optimal way is to implement the merge sort in this problem. We will follow the following steps to implement the merge sort here:

1. Find the middle of the list
2. Split the list
3. Merge it
4. Sort and Return the list

Basically the same procedure which we follow for merge sort.

Solution

In the solution we have done the following things,

1. We have declared a function to find the middle value of the list, here we are using slow and fast pointer to find it, slow pointer will point to next of head and fast will be ahead of slow, so when fast will exit the list , slow will reach the middle of list.

2. Now declare a merge function to merge the list, create a dummy node to help easily build the merge list, tail is pointer to track end of merge list.

3. Compare l1 and l2 values, the smaller node append to next of tail and move pointer in that list. Move tail to its next.

4. If one list gets exhausted before the other, append remaining nodes from non empty list to next of tail.

5. Return merged list.

6. Now, in sortList function use findMiddle function to get the middle node of list, split the list into two by making next of middle null.

7. Recursively sort both the halves.

8. Merge the list and return it.

2. Add 1 to a Linked List Number

The Problem

Firstly read the description of problem:

You are given a linked list where each element in the list is a node and have an integer data. You need to add 1 to the number formed by concatinating all the list node numbers together and return the head of the modified linked list.

So, in this question we have to take the nodes of a linked list together as a number and add 1 to it.

Approach

For adding 1 to given number we have to keep in mind that we have to handle the carry also so for that:

1. Recursively traverse to the end of LL, accumulating carry.
2. Handle the carry recursively.
3. Add carry to current node value and update it.

Solution

In this solution we have,

1. Declare a function addWithCarry which handles the carry that results from addition.

2. Add data of current node to carry returned from recursive call on next node. This give total sum with carry.

3. Update current node data to last digit of result, handling the carry for current node.

4. Return carry for next node.

5. In addOne function call addWithCarry to add one to the number and handle any carry.

6. If there is a carry left after processing all nodes, create a new node with carry value.

7. Set this new node's next to current head and return new node.

8. If there is no carry left return original head.

I hope the solutions I have provided are understandable and explanations are easy to understand.

Thank You

You can connect with me on Linkedin