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 preHeader(-1);
        preHeader.next = head;
        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;
        }
        return preHeader.next;
    }
};

Solution 2:

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


Submission errors:

 

Things to learn:

Advertisements

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 head(0);
        ListNode *cur = &head;
        while (!pq.empty()) {
            cur->next = pq.top();
            pq.pop();
            cur = cur->next;
            if (cur->next) pq.push(cur->next);
        }
        return head.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;
        }
        return divide(head, n);
    }
    ListNode* divide(ListNode *&head, int n) {
        if (n == 0) return NULL;
        if (n == 1) {
            ListNode *newHead = head;
            head = head->next;
            newHead->next = NULL;
            return newHead;
        }
        ListNode *head1 = divide(head, n/2);
        ListNode *head2 = divide(head, n - n/2);
        return merge(head1, head2);
    }
    ListNode* merge(ListNode* head1, ListNode* head2) {
        ListNode *dummy = new ListNode(0);
        ListNode *p = dummy;
        while (head1 && head2) {
            if (head1->val < head2->val) {
                p->next = head1;
                head1 = head1->next;
            } else {
                p->next = head2;
                head2 = head2->next;
            }
            p = p->next;
        }
        if (head1) p->next = head1;
        if (head2) p->next = head2;
        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;
        ListNode *newHead = head, *tail = head;
        while (tail->next) {
            len++;
            tail = tail->next;
        }
        tail->next = head;
        if (k = k % len) {
            for (int i = 0; i < len - k; i++) tail = tail->next;
        }
        newHead = tail->next;
        tail->next = NULL;
        return newHead;
    }
};

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->left = sortedListToBST(head);
        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);
        dummy->next = head;
        //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) {
            next = newHead->next;
            newHead->next = newTail;
            newTail = newHead;
            newHead = next;
            reverse_count--;
        }
        //insert into the list
        prev->next = newTail;
        start->next = newHead;
        head = dummy->next;
        delete dummy;
        return head;
    }
};

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) {
        if (!head) return;
        //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;
        while (newHead) {
            next = newHead->next;
            newHead->next = newTail;
            newTail = newHead;
            newHead = next;
        }
        //insert into the first half
        ListNode *curHead = head, *curNewHead = newTail;
        while (curHead) {
            if (curNewHead) {
                next = curNewHead->next;
                curNewHead->next = curHead->next;
                curHead->next = curNewHead;
                curNewHead = next;
                curHead = curHead->next->next;
            } else break;
        }
        return;
    }
};

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

Things to learn: