123
[LeetCode]25.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
【題意】
給定一個鏈表，一次反轉鏈表前k個節點，並返回它的修改鏈表。
如果節點的數量是不k的倍數則最終留出節點應該保持原樣，每K個一反轉，不到k個不用反轉。
【分析】
無
【代碼】
/*********************************
* 日期：2014-01-31
* 作者：SJF0115
* 題號: Reverse Nodes in k-Group
* 來源：https://oj.leetcode.com/problems/reverse-nodes-in-k-group/
* 結果：AC
* 來源：LeetCode
* 總結：
**********************************/
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
if (head == NULL || k < 2){
return head;
}
ListNode *dummy = (ListNode*)malloc(sizeof(ListNode));
dummy->next = head;
ListNode *pre = dummy,*cur = NULL,*tail = NULL;
//統計節點個數
int count = 0;
while(pre->next != NULL){
pre = pre->next;
count++;
}
//反轉次數
int rCount = count / k;
int index = 0;
//反轉元素的前一個
pre = dummy;
//反轉元素第一個即翻轉後的尾元素
tail = dummy->next;
//共進行rCount次反轉
while(index < rCount){
int i = k - 1;
//反轉
while(i > 0){
//刪除cur元素
cur = tail->next;
tail->next = cur->next;
//插入cur元素
cur->next = pre->next;
pre->next = cur;
i--;
}
pre = tail;
tail = pre->next;
index++;
}
return dummy->next;
}
};
int main() {
Solution solution;
int A[] = {1,2,3,4,5};
ListNode *head = (ListNode*)malloc(sizeof(ListNode));
head->next = NULL;
ListNode *node;
ListNode *pre = head;
for(int i = 0;i < 5;i++){
node = (ListNode*)malloc(sizeof(ListNode));
node->val = A[i];
node->next = NULL;
pre->next = node;
pre = node;
}
head = solution.reverseKGroup(head->next,5);
while(head != NULL){
printf("%d ",head->val);
head = head->next;
}
return 0;
}
【代碼】
最後更新：2017-04-03 12:54:51