Populating Next Right Pointers in Each Node II

Given a binary tree

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example 1:


Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.
Example 2:

Input: root = []
Output: []
 

Constraints:

The number of nodes in the tree is in the range [0, 6000].
-100 <= Node.val <= 100
 

Follow-up:

You may only use constant extra space.
The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

Solution

This post from Leetcode gives a nice and clear solutions.

Full code

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        // support variables
        Node *currParent = root, *baseChild, *currChild, *nextChild;
        while (currParent) {
            // skipping childless parents - get a family - up to the last node
            while (currParent->next && !currParent->left && !currParent->right) currParent = currParent->next;
            // setting the new basechild, provided we have one at all
            currChild = baseChild = currParent->left ? currParent->left : currParent->right;
            while (currChild) {
                // getting nextChild - either the right sibling of currChild or...
                if (currParent->right && currChild != currParent->right) nextChild = currParent->right;
                // the child of a following parent
                else {
                    // moving to the nextParent, if any
                    currParent = currParent->next;
                    // moving parents, if we have too
                    while (currParent && !currParent->left && !currParent->right) currParent = currParent->next;
                    // setting nextChild to be the next left/right child, if any; NULL otherwise
                    nextChild = currParent ? currParent->left ? currParent->left : currParent->right : currParent;
                }
                currChild->next = nextChild;
                currChild = nextChild;
            }
            // preparing for the next loop
            currParent = baseChild;
        }
        return root;
    }
};

Construct Binary Tree from Preorder and Inorder Traversal

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:


Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]
 

Constraints:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder and inorder consist of unique values.
Each value of inorder also appears in preorder.
preorder is guaranteed to be the preorder traversal of the tree.
inorder is guaranteed to be the inorder traversal of the tree.

Solution

Firstly, we should know that the first element in preorder list is the root of the tree. Then we can find the index of the root in inorder list. Then we can split the inorder array into left and right subtrees. The next element in preorder list will be the left child, so skip the root and split the preorder array accordingly. Recursively construct the left and right subtrees.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int findIndex(vector<int>& array, int value){
        for (int i = 0; i < array.size(); i++){
            if( array[i] == value)
                return i;
        }
        return -1;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (empty(preorder))
            return nullptr;
        // The first element in preorder list is the root of the tree
        int rootValue = preorder[0];
        TreeNode* root = new TreeNode(rootValue);

        // Find the index of the root in inorder list
        int rootIndexInOrder = findIndex(inorder, rootValue);

        // Split the inorder array into left and right subtrees
        vector <int> inorderLeft(inorder.begin(), inorder.begin() + rootIndexInOrder);
        vector <int> inorderRight(inorder.begin() + rootIndexInOrder + 1, inorder.end());

        // The next element in preorder list will be the left child, so skip the root
        // and split the preorder array accordingly
        vector <int>  preorderLeft(preorder.begin()+1, preorder.begin()+1+int(inorderLeft.size()));
        vector <int>  preorderRight(preorder.begin()+1+int(inorderLeft.size()), preorder.end());

        // Recursively construct the left and right subtrees
        root->left = buildTree(preorderLeft, inorderLeft);
        root->right = buildTree(preorderRight, inorderRight);

        return root;
    }
};

Construct Binary Tree from Inorder and Postorder Traversal

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:


Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

Solution

The post in Leetcode gives a nice and clear solutions.

The main idea is similar to the previous question, except for post order traversal, the last element is the root of the tree. Then we can find the index of the root in inorder list. Then we can split the inorder array into left and right subtrees. The next element in postorder list will be the right child, so skip the root and split the postorder array accordingly. Recursively construct the left and right subtrees.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int findIndex(vector<int>& inorder, int value){
        for (int i = 0; i < inorder.size(); i++){
            if (inorder[i] == value)
                return i;
        }
        return -1;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (empty(postorder))
            return nullptr;
        TreeNode* root = new TreeNode(postorder.back());
        postorder.pop_back();
        int inorderIndex = findIndex(inorder, root->val);
        vector<int> inorderLeft(inorder.begin(), inorder.begin()+inorderIndex);
        vector<int> inorderRight(inorder.begin()+inorderIndex+1, inorder.end());

        vector<int> postorderLeft(postorder.begin(), postorder.begin()+inorderLeft.size());
        vector<int> postorderRight(postorder.begin()+inorderLeft.size(), postorder.end());
        root -> left = buildTree(inorderLeft, postorderLeft);
        root -> right = buildTree(inorderRight, postorderRight);
        return root;
    }
};

Leetcode Study Day 33

2023-10-28

Leetcode

Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

Example 1:


Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Example 2:


Input: root = [2,1,3]
Output: [2,3,1]
Example 3:

Input: root = []
Output: []

Solution

I got the post order treversal idea from here

In his explanation, we first go to the most left node, when we reach the most left node, we go back to its parent node, then go to the right node of the parent node, if it is also the bottom node, we swap this two nodes. We repeat this process until we reach the root node.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root)
            return nullptr;
        invertTree(root->left);
        invertTree(root->right);
        TreeNode * temp = root->left;
        root -> left = root -> right;
        root -> right = temp;
        return root;
    }
};

Symmetric Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:


Input: root = [1,2,2,3,4,4,3]
Output: true
Example 2:


Input: root = [1,2,2,null,3,null,3]
Output: false

My solution

I create a function to check whether the passed nodes are the same, if so, we pass its children into this function again. If not, we return false. We call this function in the main function.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymNode(TreeNode* leftN, TreeNode* rightN){
        if (!leftN && !rightN)
            return true;
        else if (!leftN && rightN || leftN && !rightN)
            return false;
        else if (leftN->val != rightN->val)
            return false;
        else{
            return(isSymNode(leftN->left, rightN->right) && isSymNode(leftN->right, rightN->left));
        }
    }
    bool isSymmetric(TreeNode* root) {
        return(isSymNode(root->left,root->right));
    }
};

Leetcode Study Day 32

2023-10-27

Leetcode

Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:


Input: root = [3,9,20,null,null,15,7]
Output: 3
Example 2:

Input: root = [1,null,2]
Output: 2
 

Constraints:

The number of nodes in the tree is in the range [0, 104].
-100 <= Node.val <= 100

My solution

My solution is to create a recursive function, in this function, we pass two parameters, one is the node, the other is the current depth so far. If the node is null, we return the current depth. If the node is not null, we call the function recursively on the left and right child of the node, and return the maximum of the two depths.

int passDepth(TreeNode* node, int depth){
    if (!node) return depth;
    else{
        depth ++;
        return max(passDepth(node->left, depth),passDepth(node->right,depth));
    }
}

Full code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int passDepth(TreeNode* node, int depth){
        if (!node) return depth;
        else{
            depth ++;
            return max(passDepth(node->left, depth),passDepth(node->right,depth));
        }
    }

    int maxDepth(TreeNode* root) {
        int depth = 0;
        return passDepth(root,depth);
    }
};

Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:


Input: p = [1,2,3], q = [1,2,3]
Output: true
Example 2:


Input: p = [1,2], q = [1,null,2]
Output: false
Example 3:


Input: p = [1,2,1], q = [1,1,2]
Output: false

My solution

For this question, we create a recursive function to solve this question. The main idea is if the current node 1 and node 2 is null, we return true, else we return false. If the current node 1 and node 2 have the same value, we pass their left and right nodes into this function again. If the current node 1 and node 2 have different values, we return false.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q)
            return true;
        else if (!p || !q)
            return false;
        if(p->val != q->val)
            return false;
        else{
            return(isSameTree(p->left, q->left) && isSameTree(p->right, q->right));
        }
    }
};

Leetcode Study Day 31

2023-10-26

Leetcode

LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4
 

Constraints:

1 <= capacity <= 3000
0 <= key <= 104
0 <= value <= 105
At most 2 * 105 calls will be made to get and put.

Solution

The idea to implement an LRU cache with O(1) operations is to use a combination of a hash map (or dictionary) and a doubly-linked list:

Doubly-linked list: This ensures that the items can be added, removed, and moved to the front in O(1) time. The most recently accessed or added item is at the front, while the least recently accessed item is at the back.

Hash map: It’s used to achieve O(1) lookup times. The key will be the actual key of the cache, and the value will be a reference (or pointer) to the corresponding node in the doubly-linked list.

Full code:

class LRUCache {
    // initialise the node structure
    struct Node {
        int key, value;
        Node* prev;
        Node* next;
        Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };

    int capacity;
    std::unordered_map<int, Node*> map;
    Node *head, *tail;

    // Helper function to add a node after the head
    void add(Node* node) {
        node->next = head->next;
        head->next->prev = node;
        node->prev = head;
        head->next = node;
    }

    // Helper function to remove a node
    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

public:
    // initialise the LRUCahce, with two dummy nodes head and tail
    // The actual cached items lie between head and tail.
    LRUCache(int capacity) : capacity(capacity) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }
    // clean up the memory used by the doubly-linked list
    ~LRUCache() {
        while (head) {
            Node* temp = head->next;
            delete head;
            head = temp;
        }
    }

    int get(int key) {
        // if we find the key in the map
        if (map.find(key) != map.end()) {
            Node* node = map[key];
            // we remove and add the node to make sure the postion of the node is head->next
            remove(node);
            add(node);
            return node->value;
        }
        return -1;
    }

    void put(int key, int value) {
        // if we find the key in map, we delete the key and erase it in the map
        if (map.find(key) != map.end()) {
            remove(map[key]);
            delete map[key];
        }

        Node* node = new Node(key, value);
        add(node);
        map[key] = node;
        // if the amount of nodes is greater than that of capacity
        if (map.size() > capacity) {
            // the least recently used (LRU) item is the one right before the tail
            Node* lastNode = tail->prev;
            remove(lastNode);
            map.erase(lastNode->key);
            delete lastNode;
        }
    }
};


/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

Leetcode Study Day 31

2023-10-26

Leetcode

Partition List

Given the head of 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.

Example 1:


Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
Example 2:

Input: head = [2,1], x = 2
Output: [1,2]

Solution

I saw a short and elegant solution from Leetcode.

Firstly, it initialised two Listnode, than using two pointers to track the nodes that are less than x and the nodes that are greater than or equal to x. If the current value is smaller than x, we link the first node to the current node. Otherwise, we link the second node to the current node. Then, we update the current node to the next node.

Finally, we set the second node’s next node to nullptr and link the first node to the second node’s next node.

/**
 * 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* partition(ListNode* head, int x) {
        ListNode node1(0), node2(0);
        ListNode *p1 = &node1;
        ListNode *p2 = &node2;
        while(head){
            if(head->val<x){
                p1 -> next = head;
                p1 = p1 -> next;
            }
            else{
                p2 -> next = head;
                p2 = p2 -> next;
            }
            head = head -> next;
        }
        p2 -> next = nullptr;
        p1 -> next = node2.next;
        return node1.next;
    }
};

Leetcode Study Day 30

2023-10-25

Leetcode

Rotate List

Given the head of a linked list, rotate the list to the right by k places.

Example 1:


Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Example 2:


Input: head = [0,1,2], k = 4
Output: [2,0,1]
 

Constraints:

The number of nodes in the list is in the range [0, 500].
-100 <= Node.val <= 100
0 <= k <= 2 * 109

My solution

My solution is firstly use an unordered_map to store the index and the related nodes. Then I calculate the rotated link is start from which node. The I link the nodes again with the rotated index order.

/**
 * 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* rotateRight(ListNode* head, int k) {
        if (!head || k == 0) return head;
        int count = 0;
        unordered_map <int, ListNode*> listMap;
        ListNode* current = head;
        while (current){
            count += 1;
            listMap[count] = current;
            current = current -> next;
        }
        if (k%count == 0){
            return head;
        }
        int start = count + 1 - k % count;
        int new_count = start;
        ListNode* new_head = listMap[new_count];
        ListNode* new_current = new_head;
        new_count += 1;
        while( new_count != start){
            if (new_count > count){
                new_count = 1;
            }
            new_current -> next = listMap[new_count];
            new_current = new_current -> next;
            new_count += 1;
        }
        new_current -> next = nullptr;
        return new_head;
    }
};

One thing to notice is that I need to update the last node’s next to nullptr. Otherwise, it will cause a cycle in the linked list.

Improved solution from Leetcode

I found a more easy and elegant idea. In this solution, it first count the length of the link list first, then link the tail node to the head node.
Then, it will find the new head node by calculating the new head index. Finally, it will update the tail node’s next to nullptr.

In this solution, compard to mine, it doesn’t need one extra map to store index and nodes.

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null) return null;
        int listNum = 1;
        ListNode tail = head;
        
        //find tail and count listNum
        while(tail.next != null){
            listNum++;
            tail = tail.next;
        }
        tail.next = head;
        int newHeadIndex = listNum - k % listNum;

        for(int i = 0; i < newHeadIndex; i++){
            tail = tail.next;
        }
        
        head = tail.next;
        tail.next = null;

        return head;
    }
}

Leetcode Study Day 30

2023-10-25

Leetcode

Remove Duplicates from Sorted List II

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

Example 1:


Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
Example 2:


Input: head = [1,1,1,2,3]
Output: [2,3]
 

Constraints:

The number of nodes in the list is in the range [0, 300].
-100 <= Node.val <= 100
The list is guaranteed to be sorted in ascending order.

My solution

My solution is create two nodes to track which element I should delete, one is called prev, the other is called current. I also use a set to store the elements that I have seen. If the current element is already in the set, then my prev node should point to the next node of current node. Otherwise, I will add the current element to the set and update the prev node to the current node. The method of updating prev node is to check whether the next node of current node is in the set. If it is in the set, then we should not update the prev node. Or we should update the prev node to the current node.

/**
 * 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* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode();
        ListNode* current = head;
        dummy -> next = current;
        ListNode* prev = dummy;
        unordered_set <int> listSet;
        while(current){
            // if it is already stored in the set
            if (listSet.find(current->val) != listSet.end()){
                prev->next = current -> next;
                current = current->next;
            }
            else{
                listSet.insert(current->val);
                current = current -> next;
                // update the prev node
                if(current){
                    if(listSet.find(current->val) == listSet.end()){
                        prev = prev->next;
                    }
                }
            }

        }
        return dummy -> next;
    }
};

Leetcode Study Day 29

2023-10-24

Leetcode

Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:


Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:

Input: head = [1], n = 1
Output: []
Example 3:

Input: head = [1,2], n = 1
Output: [1]
 

Constraints:

The number of nodes in the list is sz.
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

My solution

My solution is firstly iterate the list to get the length of the list. Then we can calculate the index of the node we want to remove. Then we iterate the list again to remove the node.

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode* current = head;
        int count = 0;
        while (current){
            current = current->next;
            count += 1;
        }
        if (count == n)
            return head -> next;
        else if (count < n) return NULL;
        current = head;
        for (int i = 1; i < count - n; i++){
            current = current -> next;
        }
        if (current -> next)
            current -> next = current -> next -> next;
        else
            current -> next = NULL;
        return head;
    }
};

We can also use two pointers to solve this question. To be specific, we can create one pointer called fast and one pointer called slow. The fast pointer will move n steps first. Then the slow pointer will move with the fast pointer. When the fast pointer reaches the end of the list, the slow pointer will be at the node we want to remove.

Leetcode Study Day 29

2023-10-24

Leetcode

Reverse Nodes in k-Group

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

k is a positive integer and is less than or equal to the length of the linked 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 list’s nodes, only nodes themselves may be changed.

Example 1:


Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Example 2:


Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
 

Constraints:

The number of nodes in the list is n.
1 <= k <= n <= 5000
0 <= Node.val <= 1000

Solution

/**
 * 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* reverseKGroup(ListNode* head, int k) {
        // copy of the head
        ListNode* cursor = head;
        for(int i = 0; i < k; i++){
            // if the length is not enough for reverse
            if(cursor == nullptr) return head;
            cursor = cursor->next;
        }
        // copy of the head
        ListNode* curr = head;
        ListNode* prev = nullptr;
        ListNode* nxt = nullptr;
        // reverse the list
        for(int i = 0; i < k; i++){
            nxt = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nxt;
        }
        head->next = reverseKGroup(curr, k);
        return prev;
    }
};

In the reverse function, let’s used an example to explain the logic:

Consider a portion of the linked list:

A→B→C→D→E→F→…

Let’s assume k=3, so we want to reverse the first three nodes (A, B, C). After reversing:

C→B→A→D→E→F→…

Now, let’s use the code to understand how this happens:

Initial setup:
prev → null

curr → A

nxt → null

First iteration (i = 0):
nxt → B

curr
(
A’s next
)
→
null

prev
→
A

curr
→
B

After this iteration:

A←B→C→D→E→F→…

Second iteration (i = 1):
nxt
→
C
curr
(
B’s next
)
→
A

prev
→
B

curr
→
C

After this iteration:

A←B←C→D→E→F→…

Third iteration (i = 2):
nxt
→
D

curr
(
C’s next
)
→
B

prev
→
C

curr
→
D

After this iteration:

A←B←C→D→E→F→…

After these three iterations, the reversal of the first three nodes is complete. The key thing to note is how the pointers (prev, curr, and nxt) are used to reverse the pointers of the nodes in the linked list.