Given a linked list, reverse the nodes of a linked list k at a time and return its 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.
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]
Example 3:
Input: head = [1,2,3,4,5], k = 1
Output: [1,2,3,4,5]
Example 4:
Input: head = [1], k = 1
Output: [1]
Solution:
Approach:
Adding a prenode and changing 3 pointers
-1 -> 1 -> 2 -> 3 -> 4 -> 5
| | | |
pre cur nex tmp
-1 -> 2 -> 1 -> 3 -> 4 -> 5
| | | |
pre cur nex tmp
-1 -> 3 -> 2 -> 1 -> 4 -> 5
| | | |
pre cur nex tmp
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)
{
if (head == NULL || k == 1)
{
return head;
}
ListNode *p = head;
int count = 0;
while (p != NULL)
{
p = p->next;
count++;
}
ListNode *prenode = new ListNode;
prenode->val = -1;
prenode->next = head;
ListNode *pre = prenode;
ListNode *cur = prenode;
ListNode *nxt = prenode;
ListNode *temp = NULL;
while (count >= k)
{
cur = pre->next;
nxt = cur->next;
for (int i = 1; i < k; i++)
{
temp = nxt->next;
nxt->next = pre->next;
pre->next = nxt;
cur->next = temp;
nxt = temp;
}
count -= k;
pre = cur;
}
return prenode->next;
}
};
