题目介绍
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:
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
Note:
- Only constant extra memory is allowed.
- You may not alter the values in the list’s nodes, only nodes itself may be changed.
解
1 | /** |
2 | * Definition for singly-linked list. |
3 | * struct ListNode { |
4 | * int val; |
5 | * ListNode *next; |
6 | * ListNode(int x) : val(x), next(NULL) {} |
7 | * }; |
8 | */ |
9 | class Solution { |
10 | public: |
11 | ListNode* reverseKGroup(ListNode* head, int k) { |
12 | if (k < 2) { |
13 | return head; |
14 | } |
15 | ListNode first(-1); |
16 | first.next = head; |
17 | ListNode* pre = &first; |
18 | ListNode* node = pre; |
19 | for (int i = 0; i < k; i++) { |
20 | if (node->next == NULL) { |
21 | return pre->next; |
22 | } |
23 | node = node->next; |
24 | } |
25 | ListNode* tmp = head; |
26 | do { |
27 | tmp = head->next; |
28 | head->next = tmp->next; |
29 | tmp->next = pre->next; |
30 | pre->next = tmp; |
31 | } while (tmp != node); |
32 | head->next = reverseKGroup(head->next, k); |
33 | return pre->next; |
34 | } |
35 | }; |
Runtime: 16 ms
