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.

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.

每k个节点为一组，组内进行链表翻转。

递归的思路。

先找到下一个group的节点，然后把目前的k个节点翻转了之后，递归处理后面的节点。下面是递归处理的过程。

链表翻转的过程：

---

C++版本。参考博客。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
ListNode* reverseKGroup(ListNode* head, int k) {
        if(k<=1||!head||!head->next) return head;
        ListNode *nextgroup = head;
        
        //nextgroup指向下一个group 
        for(int i=0;i<k;i++){
            if(nextgroup){
                nextgroup = nextgroup->next;
            }else				{//如果不足k个的话，直接返回 
                return head;
            }
        }
       
        ListNode *pre = reverseKGroup(nextgroup,k);//记录前一个 
        ListNode *cur = head;//记录当前 
        ListNode *nxt = NULL;//记录下一个 
        //翻转
        while(cur!=nextgroup){
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
}

只是翻转链表的代码

/*
typedef struct Node{
	int value;
	Node *next;
}Node,*LinkList;
*/
//翻转链表
Node *reverseLinkList(Node *head){
	Node *res = NULL;
	Node *cur = head;
	Node *pre = NULL;
	while(cur){
		Node *nxt = cur->next;//原来链表的下一个 
		if(!nxt){
			res = cur;
		}
		cur->next = pre;//前一个放到当前链表的next 
		pre = cur;
		cur = nxt;
	}
	return res;
}