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:
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (!head || k == 1) return head;
int n = 0;
ListNode *cur = &preHeader, *next, *pre = &preHeader;
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:
/**
* Definition for singly-linked list.
* 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);
ListNode *cur = &head;
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:
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
ListNode *p = head;
int n = 0;
while (p) {
n++;
p = p->next;
}
}
ListNode* divide(ListNode *&head, int n) {
if (n == 0) return NULL;
if (n == 1) {
}
ListNode *head2 = divide(head, n - n/2);
}
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:
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (!head) return NULL;
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:
/**
* Definition for singly-linked list.
* 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:
TreeNode* sortedListToBST(ListNode* head) {
if (!head) return NULL;
ListNode *fast = head, *slow = head, *pre = NULL;
while(fast && fast->next) {
fast = fast->next->next;
pre = slow;
slow = slow->next;
}
if (pre) pre->next = NULL;
else head = 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:
/**
* Definition for singly-linked list.
* 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:
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
//find the middle
ListNode *fast = head, *slow = head;
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: