# 25. Reverse Nodes in k-Group

Difficulty: Hard

Frequency: N/A

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: `1->2->3->4->5`

For k = 2, you should return: `2->1->4->3->5`

For k = 3, you should return: `3->2->1->4->5`

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
int n = 0;
while (cur = cur->next) n++;
while (n >= k) {
cur = pre->next;
next = cur->next;
for (int i = 1; i < k; i++) {
cur->next = next->next;
next->next = pre->next;
pre->next = next;
next = cur->next;
}
pre = cur;
n -= k;
}
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

# 023. Merge k Sorted Lists

Difficulty: Hard

Frequency: N/A

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
private:
struct compare {
bool operator() (const ListNode* l, const ListNode* r) {
return l->val > r->val;
}
};
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, compare> pq;
for (ListNode* l : lists) if (l) pq.push(l);
while (!pq.empty()) {
cur->next = pq.top();
pq.pop();
cur = cur->next;
if (cur->next) pq.push(cur->next);
}
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 148. Sort List

Difficulty: Medium

Frequency: N/A

Sort a linked list in O(n log n) time using constant space complexity.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
int n = 0;
while (p) {
n++;
p = p->next;
}
}
ListNode* divide(ListNode *&head, int n) {
if (n == 0) return NULL;
if (n == 1) {
}
}
ListNode *dummy = new ListNode(0);
ListNode *p = dummy;
} else {
}
p = p->next;
}
return dummy->next;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 061. Rotate List

Difficulty: Medium

Frequency: N/A

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given `1->2->3->4->5->NULL` and k = `2`,
return `4->5->1->2->3->NULL`.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
int len = 1;
while (tail->next) {
len++;
tail = tail->next;
}
if (k = k % len) {
for (int i = 0; i < len - k; i++) tail = tail->next;
}
tail->next = NULL;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 109. Convert Sorted List to Binary Search Tree

Difficulty: Medium

Frequency: N/A

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
while(fast && fast->next) {
fast = fast->next->next;
pre = slow;
slow = slow->next;
}
if (pre) pre->next = NULL;
TreeNode *root = new TreeNode(slow->val);
root->right = sortedListToBST(slow->next);
return root;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 092. Reverse Linked List II

Difficulty: Medium

Frequency: N/A

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given `1->2->3->4->5->NULL`, m = 2 and n = 4,

return `1->4->3->2->5->NULL`.

Note:
Given m, n satisfy the following condition:
1 ≤ mn ≤ length of list.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode *dummy = new ListNode(0);
//find the start
ListNode *start = dummy, *prev = NULL;
int start_node = m;
while (start && start_node > 0) {
prev = start;
start = start->next;
start_node--;
}
//reverse the part
ListNode *newHead = start, *newTail = NULL, *next = NULL;
int reverse_count = n - m + 1;
while (newHead && reverse_count > 0) {
reverse_count--;
}
//insert into the list
prev->next = newTail;
delete dummy;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 143. Reorder List

Difficulty: Medium

Frequency: N/A

Given a singly linked list L: L0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-2→…

You must do this in-place without altering the nodes’ values.

For example,
Given `{1,2,3,4}`, reorder it to `{1,4,2,3}`.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
//find the middle
while (fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
}
ListNode *middle = slow->next;
slow->next = NULL;
//reverse the second half
ListNode *newHead = middle, *newTail = NULL, *next = NULL;
}
//insert into the first half
} else break;
}
return;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 086. Partition List

Difficulty: Medium

Frequency: N/A

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given `1->4->3->2->5->2` and x = 3,
return `1->2->2->4->3->5`.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode *dummy = new ListNode(INT_MIN), *middle_point = dummy, *cur = dummy, *prev = dummy;
bool passed_middle = false;
while (cur) {
if (passed_middle) {
if (cur->val < x) {
prev->next = cur->next;
cur->next = middle_point->next;
middle_point->next = cur;
middle_point = middle_point->next;
cur = prev->next;
} else {
prev = cur;
cur = cur->next;
}
} else {
if (cur->val < x) {
prev = cur;
} else {
passed_middle = true;
middle_point = prev;
prev = cur;
}
cur = cur->next;
}
}
delete dummy;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 147. Insertion Sort List

Difficulty: Medium

Frequency: N/A

Sort a linked list using insertion sort.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *dummy = new ListNode(INT_MIN);
while (cur) {
if (!curNext) {
break;
} else if (head->val < curNext->val) {
break;
} else {
cur = cur->next;
curNext = curNext->next;
}
}
}
delete dummy;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 082. Remove Duplicates from Sorted List II

Difficulty: Medium

Frequency: N/A

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given `1->2->3->3->4->4->5`, return `1->2->5`.
Given `1->1->1->2->3`, return `2->3`.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:

/**
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *dummy = new ListNode(0);
ListNode *prev = dummy, *tmp = NULL;
bool delete_self = false;
delete tmp;
delete_self = true;
} else if (delete_self) {
delete tmp;
delete_self = false;
} else {
}
}
delete dummy;
}
};
[cpp]

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: