Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
54 lines (46 sloc) 1.55 KB
problem:
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:
//这题要求在原链上修改,也就是够k个组成的部分进行reverse,不够的则保持
//用指针的指针绑定头结点,然后依次修改链表,最后返回头结点
////////////////////////////////////
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode *reverseKGroup(ListNode *head, int k)
{
if(k < 2)
return head;
ListNode **pNode = &head;
while(*pNode)
{
ListNode *pEnd = *pNode;
for(int i = 1; pEnd && i < k; ++i)
pEnd = pEnd->next;
if(pEnd) //翻转
{
ListNode *subTail = *pNode; //刚开始的头结点一步步形成翻转序列的尾结点
for(int j = 1; j < k; ++j)
{
ListNode *pCur = subTail->next; //每次待翻转结点都是subHead的next结点
subTail->next = pCur->next;
pCur->next = *pNode;
*pNode = pCur; //pNode每次更新为翻转序列的当前头结点
}
pNode = &(subTail->next);
}
else
break; //不足k个,保持链表结点不变
}
return head;
}