As I have covered a few topics in the previous article, I'll cover the remaining pattern and problems here.
As seen in the above example, we reverse the linked list first, then we will add carry(=1) to the node's data. But do we need to add one to all the next nodes?
No right, if node data == 9, we will update the node's data to 0, and move to the next node. If node data <=8, we will add one to node data and break the traversal.
Code
static Node addOne(Node head)
{
Node res = head;
Node temp = null, prev = null;
int carry = 1, sum;
while (head != null)
{
//Updating the node data by +1
sum = carry + head.data;
carry = (sum >= 10) ? 1 : 0;
sum = sum % 10;
head.data = sum;
temp = head;
head = head.next;
}
if (carry > 0)
temp.next = newNode(carry);
return res;
}
In order to find, If the given linked list, is circular or not, We store the head next in a temp node, and traversal the linked list after the head, If while traversing the current node equals to head, return True, else we return False.
Code
class Solutioon{
static boolean isCircular(Node head)
{
if (head == null)
return true;
Node node = head.next;
while (node != null && node != head)
node = node.next;
return (node == head);
}
}
Unlike the removal of the duplicate from the sorted linked lists, here we use an additional data structure(Set). We will initialize a prev to store the previous node, We do a normal traversal on the linked list, if the node is not found in the set, we add it to the set and update the prev to the current node, and move forward. If the current node is found in the set, then skip the current node, i.e make prev.next to the current.next, thus skipping the current node.
Code
class Solution
{
//Function to remove duplicates from unsorted linked list.
public Node removeDuplicates(Node head)
{
// Your code here
Set<Integer> checker = new HashSet<>();
Node prev=null;
Node output = head;
while(head!=null){
if(checker.contains(head.data)){
prev.next = head.next;
}
else{
checker.add(head.data);
prev=head;
}
head=head.next;
}
return output;
}
}
We use intuition based on Floyd’s Cycle detection algorithm. At first, we detect Loop using Floyd’s Cycle detection algorithm and get the pointer to a loop node. Then we count the number of nodes in the loop. Let the count be k. Fix one pointer to the head and another to a kth node from the head. Move both pointers at the same pace, they will meet at the loop starting node. Get a pointer to the last node of the loop and make the next of it NULL.
Code
//Solution from GFG.
class Solution{
boolean detectAndRemoveLoop(Node node)
{
Node slow = node, fast = node;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
removeLoop(slow, node);
return true;
}
}
return false;
}
// Function to remove loop
void removeLoop(Node loop, Node head)
{
Node ptr1 = loop;
Node ptr2 = loop;
int k = 1, i;
while (ptr1.next != ptr2) {
ptr1 = ptr1.next;
k++;
}
ptr1 = head;
ptr2 = head;
for (i = 0; i < k; i++) {
ptr2 = ptr2.next;
}
while (ptr2 != ptr1) {
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
// Get pointer to the last node
while (ptr2.next != ptr1) {
ptr2 = ptr2.next;
}
ptr2.next = null;
}
}
Here we will use the two pointers approach by always moving the slow pointer by one, and the fast pointer by two node(s). Such that when the fast is at null, we can move the or point the slow next to slow next's next.
Algorithm
- Create a dummy head, and initialize slow and fast pointers as dummy;
- Traverse the ListNodes starting from dummy by the afore-mentioned two pointers, slow forwards 1 step and fast forwards 2 steps per iteration;
- Terminate the traversal till fast.next or fast.next.next is null, and now slow points to the previous node of the middle node; remove the middle node;
- Return dummy.next as the result.
Code
class Solution{
public ListNode deleteMiddle(ListNode head) {
ListNode dummy = new ListNode(-1), slow = dummy, fast = dummy;
dummy.next = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
This problem can be solved by intuition based on the merge function from merge sort, which basically merges two sorted arrays. Similary here we create a new output linked list, and add new nodes to that linked list on the basis of comparisons of two nodes from List1 and List2.
Code
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//Define a new Node
ListNode answer = new ListNode(-1);
ListNode newNode = answer;
//If list1 has no element then add list2 to new node
if (list1 == null)
return newNode.next = list2;
//If list2 has no element then add list1 to new node
if (list2 == null)
return newNode.next = list1;
//Use Merge sort logic to merge nodes value
while (list1 != null && list2 != null)
{
if (list1.val <= list2.val)
{
newNode.next = list1;
list1 = list1.next;
}
else
{
newNode.next = list2;
list2 = list2.next;
}
newNode = newNode.next;
}
//If any node left in list1
if (list1 != null)
newNode.next = list1;
//If any node left in list2
if (list2 != null)
newNode.next = list2;
return answer.next;
}
}
The brute-force approach for this problem is to store all values of nodes in an array, sort the array and replace or overwrite the values of nodes while traversing. But however the Time Complexity is O(N) + O(nlogn) + O(N) and
Space Complexity is O(N) + O(N)(Auxilary stack space for recursion)
An efficient way to solve this problem is to use merge sort on the linked list.
Code
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode mid = getMid(head);
ListNode left = sortList(head);
ListNode right = sortList(mid);
return merge(left, right);
}
ListNode merge(ListNode list1, ListNode list2) {
ListNode dummyHead = new ListNode();
ListNode tail = dummyHead;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
tail.next = list1;
list1 = list1.next;
tail = tail.next;
} else {
tail.next = list2;
list2 = list2.next;
tail = tail.next;
}
}
tail.next = (list1 != null) ? list1 : list2;
return dummyHead.next;
}
ListNode getMid(ListNode head) {
ListNode midPrev = null;
while (head != null && head.next != null) {
midPrev = (midPrev == null) ? head : midPrev.next;
head = head.next.next;
}
ListNode mid = midPrev.next;
midPrev.next = null;
return mid;
}
}
Why Merge Sort but not Quick Sort?
While using Merge Sort we use the middle element to carry out the splitting and performing actions, but in Quick Sort the pivot is probably the smaller element, and accessing by indexes takes O(N) in the linked list, thus it is preferred to use the Merge over Quick.
In order to swap every two nodes in the linked list, the brute force is to store the values of nodes in an array, increase the step by +=2, then swap values of every first and second node with i+1 and i respectively.
Time Complexity is O(N) + O(N/2)
Space Complexity is O(N)
An efficient way to solve this problem is to traverse till last but one node, and swap the values of the nodes encountered in between, move the current node by two nodes ahead.
Code
class Solution{
void pairWiseSwap(Node head)
{
Node temp = head;
/* Traverse only till there are atleast 2 nodes left */
while (temp != null && temp.next != null) {
/* Swap the data */
int k = temp.data;
temp.data = temp.next.data;
temp.next.data = k;
temp = temp.next.next;
}
}
}
Additional problems on Linked List
- The intersection of 2 linked lists.
- Split a circular linked list into two halves.
- Rotate a linked list by k positions.
- Delete the n-th node from the end of the linked list.
- Flatten a linked list.