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个数的链段，然后对该链段进行反转。链表反转采用头插法，需要指明头结点位置，判断插入是否终止的条件。头结点需要不断更新。
解题
c++版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode dummy(-1);
dummy.next=head;
int count=0;
ListNode *pre,*cross;
pre=&dummy;
cross=head;
while(cross){
count++;
if(count%k==0){
pre=reverse(pre,cross->next);
cross=pre->next;
}
else{
cross=cross->next;
}
}
return dummy.next;
}
ListNode* reverse(ListNode* head, ListNode *next1){
ListNode *pre,*cur;
pre=head->next;
cur=pre->next;
while(cur!=next1){
pre->next=cur->next;
cur->next=head->next;
head->next=cur;
cur=pre->next;
}
return pre;
}
};
|
Python 版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
class Solution:
def reverseKGroup(self, head, k):
if not head or k<=1:
return head
dummy=ListNode(-1)
dummy.next=head
pre=dummy
cross=head
count=0
while cross:
count+=1
if(count%k==0):
pre=self.reverse(pre,cross.next)
cross=pre.next
else:
cross=cross.next
return dummy.next
def reverse(self,head,next1):
pre=head.next
cur=pre.next
while cur!=next1:
pre.next=cur.next
cur.next=head.next
head.next=cur
cur=pre.next
return pre
|
