> For the complete documentation index, see [llms.txt](https://dsa-cpp.gitbook.io/nafees/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dsa-cpp.gitbook.io/nafees/linked-list/problems.md).
# Problems
## `Q1:` [Reverse Linked List](https://www.codingninjas.com/studio/problems/reverse-the-singly-linked-list_799897?)
## [Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/)
```cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// handle first Node
if(head == nullptr || head -> next == nullptr) return head;
ListNode* prev = head;
ListNode* cur = head -> next;
ListNode* temp = head -> next -> next;
prev -> next = nullptr;
// handle middle Nodes
while(temp != nullptr) {
cur -> next = prev;
prev = cur;
cur = temp;
temp = temp -> next;
}
// handle last Node
cur -> next = prev;
head = cur;
return head;
}
};
```
## `Q2:` Middle Of Linked List
Approach # 01
```cpp
int getLength(Node* head){
int cnt = 0;
while(head != NULL){
cnt++;
head = head->next;
}
return cnt;
}
Node *findMiddle(Node *head) {
int mid = getLength(head)/2;
//int cnt = 0;
while(mid-- != 0) // (count++ < mid)
head = head->next;
return head; // returning pointer pointing to the middle of the list
}
i/p = [1,2,3,4,5]
o/p = [3,4,5]
T.C = O(n) + O(n/2)
= O(n) + O(n)
= 2 O(n)
= O(n)
```
## `Q3:` [Sort List](https://leetcode.com/problems/sort-list/)
```cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void getSize(ListNode* head, int& size){
ListNode* temp = head;
int i = 0;
while(temp != nullptr){
temp = temp -> next;
i++;
}
size = i;
}
ListNode* sortList(ListNode* head) {
int size;
getSize(head, size);
for(int i = 1; i < size;i++) {
ListNode* prev = nullptr;
ListNode* cur = head;
ListNode* nxt = cur -> next;
bool isSorted = true;
for(int j = 0; j < size-i; j++) {
if(cur -> val > nxt -> val){
cur -> next = nxt -> next;
nxt -> next = cur;
isSorted =false;
if(prev != nullptr) prev -> next = nxt;
else head = nxt;
cur = nxt;
nxt = nxt -> next;
}
prev = cur;
cur = cur -> next;
nxt = nxt -> next;
}
if(isSorted) break;
}
return head;
}
};
```
## `Q4:` [Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list/)
```cpp
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;
while(cur != nullptr) {
if(prev != nullptr && cur -> val == prev -> val) {
prev -> next = cur -> next;
ListNode* temp = cur;
cur = cur -> next;
delete temp;
continue;
}
prev = cur;
cur = cur -> next;
}
return head;
}
};
```
## Q5: [Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
```cpp
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head == NULL || head -> next == NULL) return head;
ListNode* prev = NULL;
ListNode* cur = head;
ListNode* nxt = head -> next;
bool isFirstElemDup = false;
if(cur -> val == nxt -> val) isFirstElemDup = true;
while(nxt != NULL) {
bool isDup = false;
if(cur -> val == nxt -> val) {
isDup = true;
recheck:
while(nxt != NULL && nxt -> val == cur -> val) {
cur = nxt;
nxt = nxt -> next;
}
if(nxt != NULL) {
if (nxt -> next != NULL && nxt -> next -> val == cur -> next -> val) {
cur = nxt;
nxt = nxt -> next;
goto recheck;
}
}
}
if(isFirstElemDup) {
prev = head = nxt;
isFirstElemDup = false;
}
else if(isDup) prev -> next = nxt;
if(!isDup) prev = cur;
else prev = nxt;
cur = nxt;
if(nxt != NULL) nxt = nxt -> next;
}
return head;
}
};
```
## Q6: [148. Sort List](https://leetcode.com/problems/sort-list/)
```cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
ListNode* t1 = head;
while(t1 != nullptr){
ListNode* t3;
ListNode* t2 = t1 -> next;
int curVal = t1 -> val;
bool isFind = false;
while(t2 != nullptr) {
if(t2 -> val < curVal) {
curVal = t2 -> val;
t3 = t2;
isFind = true;
}
t2 = t2 -> next;
}
if(isFind)
swap(t1 -> val, t3 -> val);
t1 = t1 -> next;
}
return head;
}
};
```
## Q7: [19. Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)
```cpp
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(head == nullptr) return head;
if(head -> next == nullptr && n == 1) {
head = nullptr;
return head;
}
int count = 0;
ListNode* t1 = head;
while(t1 != nullptr) {
count++;
t1 = t1 -> next;
}
ListNode* t2 = head;
while(count > n ) {
count--;
t1 = t2;
t2 = t2 -> next;
}
// for first node
if(t1 == nullptr) {
head = head -> next;
t1 = t2 = nullptr;
return head;
}
// for middle and last node
t1 -> next = t2 -> next;
return head;
}
};
```
## Q8: [Rotate List](https://leetcode.com/problems/rotate-list/)
```cpp
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(head == NULL || head -> next == NULL || k == 0) return head;
ListNode* prev = head;
ListNode* cur = head;
int n = 0;
while(cur != nullptr) {
cur = cur -> next;
n++;
}
if (k % n == 0) return head; // 10,000 % 5 = 0
if(n < k) k %= n; // 5 < 98553 --> k = 98553 % 5 = 3 steps
cur = head;
for(int i = n; i > k; i--) {
prev = cur;
cur = cur -> next;
}
ListNode* curHead = cur;
while(cur -> next != nullptr) {
cur = cur -> next;
}
prev -> next = nullptr;
cur -> next = head;
head = curHead;
return head;
}
};
```
## Q9: [Reverse Nodes in k-Group](https://leetcode.com/problems/reverse-nodes-in-k-group/)
```cpp
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
stack st;
ListNode* temp = nullptr;
ListNode* tempHead;
ListNode* t1 = head;
int count = 0;
while(t1 != nullptr) {
tempHead = t1;
while(count < k && t1 != nullptr) {
st.push(t1);
t1 = t1 -> next;
count++;
}
if(count < k) return head;
while(!st.empty()) {
if(temp == nullptr)
temp = head = st.top();
else {
temp -> next = st.top();
temp = temp -> next;
}
st.pop();
}
tempHead -> next = t1;
count = 0;
}
return head;
}
};
```
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:
```
GET https://dsa-cpp.gitbook.io/nafees/linked-list/problems.md?ask=&goal=
```
`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.