DSA Sheet By Arsh
Solution of Linked List Medium Level Problem
shivani patel
SNo. Problem Statement
1. Medium Level : Add Two Numbers.
Code:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode* dummy=new ListNode(0);
ListNode* tmp=dummy;
int carry=0;
while(l1!=NULL || l2!=NULL || carry)
{
int sum=0;
if(l1!=NULL)
{
sum+=l1->val;
l1=l1->next;
}
if(l2!=NULL)
{
sum+=l2->val;
l2=l2->next;
}
sum+=carry;
carry=sum/10;
ListNode* node=new ListNode(sum%10);
tmp->next=node;
tmp=tmp->next;
}
return dummy->next;
}
2. Medium Level : Copy List with Random Pointer.
Code :
SHIVANI PATEL 1
DSA Sheet By Arsh
Solution of Linked List Medium Level Problem
shivani patel
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
class Solution {
public:
Node* copyRandomList(Node* head) {
Node *curr=head,*front=head;
while(curr!=NULL)
{
front=curr->next;
Node *copy=new Node(curr->val);
curr->next=copy;
copy->next=front;
curr=front;
}
curr=head;
while(curr!=NULL)
{
if(curr->random!=NULL)
{
curr->next->random=curr->random->next;
}
curr=curr->next->next;
}
curr=head;
Node *dummy=new Node(0);
Node *copy=dummy;
while(curr!=NULL)
{
front=curr->next->next;
copy->next=curr->next;
curr->next=front;
copy=copy->next;
curr=curr->next;
}
return dummy->next;
SHIVANI PATEL 2
DSA Sheet By Arsh
Solution of Linked List Medium Level Problem
shivani patel
}
};
3. Medium Level : Add Two Numbers II.
Code:
Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
stack<int>s1;
stack<int>s2;
ListNode* ans=new ListNode(0);
while(l1)
{
st1.push(l1->val);
l1=l1->next;
}
while(l2)
{
st2.push(l2->val);
l2=l2->next;
}
int sum=0;
while(!st1.empty() || !st2.empty())
{
if(!st1.empty())
{
sum+=st1.top();
st1.pop();
}
if(!st2.empty())
{
sum+=st2.top();
st2.pop();
}
SHIVANI PATEL 3
DSA Sheet By Arsh
Solution of Linked List Medium Level Problem
shivani patel
ans->val=sum%10;
sum/=10;
ListNode* head=new ListNode(sum);
head->next=ans;
ans=head;
}
return ans->val==0?ans->next:ans;
}
4. Medium Level : Reverse Linked List II.
Code:
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
ListNode* reverse(ListNode* head){
ListNode* prev = NULL, *next = NULL, *current = head;
while(current != NULL){
next = current->next;
current->next = prev;
prev = current;
current = next;
return prev;
}
ListNode* reverseBetween(ListNode* head, int left, int right) {
if(head == NULL || left == right){
return head;
}
ListNode* prev, *tail = NULL, *temp = NULL;
ListNode dummy(NULL);
prev = &dummy;
dummy.next = head;
for(int i=0; i < left-1; i++){
SHIVANI PATEL 4
DSA Sheet By Arsh
Solution of Linked List Medium Level Problem
shivani patel
prev = prev->next;
}
tail = prev->next;
for(int i=0; i< right - left;i++){
temp = prev->next;
prev->next = tail->next;
tail->next = tail->next->next;
prev->next->next = temp;
}
return dummy.next;
}
5. Medium Level : Reorder List.
Code:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
void reorderList(ListNode* head)
{
stack<int>s;
ListNode* curr=head;
while(curr)
{
s.push(curr);
curr=curr->next;
}
curr=head;
int n=s.size();
ListNode* next;
for(int i=0;i<n/2;i++)
{
next=curr->next;
curr->next=s.top();
s.pop();
curr=curr->next;
curr->next=next;
curr=curr->next;
SHIVANI PATEL 5
DSA Sheet By Arsh
Solution of Linked List Medium Level Problem
shivani patel
}
curr->next=NULL;
}
6. Medium Level : Remove Nth Node From End of List.
Code :
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
ListNode* removeNthFromEnd(ListNode* head, int n)
{
ListNode* dummy=neew ListNode();
dummy->next=head;
int c=0;
while(dummy->next!=NULL)
{
dummy=dummy->next;
c++;
}
int num=c-n;
ListNode* tmp=new ListNode();
tmp->next=head;
while(num!=0)
{
tmp=tmp->next;
num--;
}
if(c!=n)
{
tmp->next=tmp->next->next;
return head;
}
else
{
head=head->next;
return head;
}
}
SHIVANI PATEL 6
DSA Sheet By Arsh
Solution of Linked List Medium Level Problem
shivani patel
7. Medium Level : Flatten a Multilevel Doubly Linked List.
Code :
Input: head = [1,2,null,3]
Output: [1,3,2]
Explanation: The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:
Node* flatten(Node* head) {
Node* final = head;
stack<Node*> s;
Node* temp;
while(head != nullptr){
if(head->child != nullptr){
if(head->next != nullptr){
temp = head->next;
s.push(temp);
}
head->child->prev = head;
head->next = head->child;
head->child = nullptr;
}
if(!s.empty() && head->next == nullptr){
head->next = s.top();
head->next->prev = head;
s.pop();
}
head = head->next;
}
return final;
}
8. Medium Level : Partition List.
Code:
Input: head = [1,4,3,2,5,2], x = 3
SHIVANI PATEL 7
DSA Sheet By Arsh
Solution of Linked List Medium Level Problem
shivani patel
Output: [1,2,2,4,3,5]
ListNode* partition(ListNode* head, int x) {
ListNode *small_head=new ListNode(0);
ListNode *small=small_head;
ListNode *high_head=new ListNode(0);
ListNode *high=high_head;
while(head!=NULL)
{
if(head->val<x)
{
small->next=head;
small=small->next;
}
else
{
high->next=head;
high=high->next;
}
head=head->next;
}
high->next=NULL;
small->next=high_head->next;
return small_head->next;
}
9. Medium Level : Remove Duplicates from Sorted List II.
Code:
Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
ListNode* deleteDuplicates(ListNode* head)
{
if(head==NULL)
SHIVANI PATEL 8
DSA Sheet By Arsh
Solution of Linked List Medium Level Problem
shivani patel
return NULL;
unordered_map<int,int>m;
ListNode* tmp=head;
while(tmp)
{
m[tmp->val]++;
tmp=tmp->next;
}
ListNode* ans=new ListNode(-1);
ListNode* tmp2=ans;
for(auto i:m)
{
if(i.second==1)
temp2->next = new ListNode(i.first);
temp2 = temp2->next;
}
return ans->next;
}
10. Medium Level: Rearrange a Linked List in Zig-Zag fashion
Code:
Input: 1->2->3->4
Output: 1->3->2->4
Explanation : 1 and 3 should come first before 2 and 4 in
zig-zag fashion, So resultant linked-list will be 1->3->2-
>4.
Input: 11->15->20->5->10
Output: 11->20->5->15->10
Node* zigzag(Node* head, bool flag)
{
if(!head || !head->next)
return head;
if(flag==1)
{
if(head->data > head->next->data)
SHIVANI PATEL 9
DSA Sheet By Arsh
Solution of Linked List Medium Level Problem
shivani patel
{
swap(head->data,head->next->data);
return zigzag(head->next,!flag);
}
}
else {
if (head->data < head->next->data)
swap(head->data, head->next->data);
return zigzag(head->next, !flag);
}
}
11. Medium Level: Sort List.
Code:
Input: head = [4,2,1,3]
Output: [1,2,3,4]
ListNode* sortList(ListNode* head)
{
if(head==NULL || head->next==NULL)
return head;
vector<int>v;
while(head!=NULL)
{
v.push_back(head->val);
head=head->next;
}
sort(v.begin(),v.end());
ListNode* ans=new ListNode(v[0]);
ListNode* start=ans;
for(int i=1;i<v.size();i++)
{
ans->next=new ListNode(v[i]);
ans=ans->next;
}
return start;
}
12. Medium Level: Sort List.
SHIVANI PATEL 10
DSA Sheet By Arsh
Solution of Linked List Medium Level Problem
shivani patel
Code:
Input: 17->15->8->12->10->5->4->1->7->6->NULL
Output: 8->12->10->4->6->17->15->5->1->7->NULL
Input: 8->12->10->5->4->1->6->NULL
Output: 8->12->10->4->6->5->1->NULL
ListNode* sortList(ListNode* head)
{
if(head==NULL || head->next==NULL)
return head;
vector<int>v;
while(head!=NULL)
{
v.push_back(head->val);
head=head->next;
}
sort(v.begin(),v.end());
ListNode* ans=new ListNode(v[0]);
ListNode* start=ans;
for(int i=1;i<v.size();i++)
{
ans->next=new ListNode(v[i]);
ans=ans->next;
}
return start;
}
13. Medium Level: Rearrange a given linked list in-place.
Code:
Input: 1 -> 2 -> 3 -> 4
Output: 1 -> 4 -> 2 -> 3
Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 5 -> 2 -> 4 -> 3
void rearrange(Node* head)
SHIVANI PATEL 11
DSA Sheet By Arsh
Solution of Linked List Medium Level Problem
shivani patel
{
if (head == NULL)
return;
Node *prev = head, *curr = head->next;
while (curr) {
if (prev->data > curr->data)
swap(prev->data, curr->data);
if (curr->next && curr->next->data > curr->data)
swap(curr->next->data, curr->data);
prev = curr->next;
if (!curr->next)
break;
curr = curr->next->next;
}
}
SHIVANI PATEL 12
