LeetCode Reverse Nodes in k-Group: Pointer Manipulation

Overview

LeetCode Reverse Nodes in k-Group solution is a good one to test your pointer manipulation skills, be careful about tail setting to NULL and concatenation.

LeetCode Reverse Nodes in k-Group

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

Solution Analysis: Pointer Manipulation

There is on innovative algorithm involved, just simulate the process. But be careful handling the pointers. I give the implementation which is accepted by LeetCode OJ directly for this everse Nodes in k-Group problem followed by more elaborations.

class Solution {
    public:
        ListNode *reverse(ListNode *p1, ListNode *p2, int k) {
               ListNode *prev = p1;
               ListNode *curr = p1->next;
               ListNode *next = p1->next;

               p1->next = NULL;
               for (int i = 1; i < k; ++i) {
                   next = curr->next;
                   curr->next = prev;
                   prev = curr;
                   curr = next;
               }
               return p2;
        }
        ListNode *reverseKGroup(ListNode *head, int k) {
            if (k <= 1 || NULL == head)
                return head;

            ListNode s(0);
            s.next = head;
            ListNode *p1(head), *p2(head);
            ListNode *t(&s), *h(head);

            while (h) {
                for (int i = k - 1; i > 0 && p2; --i)
                    p2 = p2->next;
                if (p2) {
                    h = p2->next;
                    t->next = reverse(p1, p2, k);
                    t = p1;
                    p2 = p1 = h;
                }
                else {
                    t->next = p1;
                    h = p2;
                }
            }
            return s.next;
        }
};

Elaboration:

  1. As long as you use finite number of pointers, you are only using constant memory, so use enough number of pointers to make the logic of your program as clear as possible. Don’t try to use less pointers to say constant memory because the clear issue is more important when involving pointers which is very easy to make mistakes
  2. Don’t forget the set the tail of the reversed portion as NULL since it might be the last portion
  3. There might be infinite loop in the list when careless handling the pointers. Always check and make sure there is no loop in the linked list!

Summary

LeetCode Reverse Nodes in k-Group solution is a good one to test your pointer manipulation skills, be careful about tail setting to NULL and concatenation.

Written on May 26, 2013