题目： 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： 首先遍历链表得到链表的长度num，然后每次k个一个小组进行转换，如果长度小于k个结束循环 每次k个小组中交换结点需要循环k-1次 如1->2->3 转换到3->2->1 需要2次循环 1->2->3 到 2->1->3 到 3->2->1 每次将1往后移一位，然后将1后面的元素移到队首 第一次大循环 第一次小循环 第二次小循环 第二次大循环
c++：
/** * 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; ListNode* pre = &dummy; ListNode* cur = pre; int num = 0; while(cur = cur->next) num++; while(num >= k){ cur = pre->next; for(int i = 1; i < k; i++){ ListNode* t = cur->next; cur->next = t->next; t->next = pre->next; pre->next = t; } pre = cur; num -= k; } return dummy.next; } };java：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode pre = dummy; ListNode cur = pre; int num = 0; while((cur = cur.next) != null) num++; while(num >= k){ cur = pre.next; for(int i = 1; i < k; i++){ ListNode t = cur.next; cur.next = t.next; t.next = pre.next; pre.next = t; } pre = cur; num -= k; } return dummy.next; } }Python： 直接 while cur = cur.next:报错 原因：表达式中不能有赋值
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def reverseKGroup(self, head, k): """ :type head: ListNode :type k: int :rtype: ListNode """ dummy = ListNode(-1) dummy.next = head pre = dummy cur = pre num = 0 while cur.next: num += 1 cur = cur.next while num >= k: cur = pre.next for i in xrange(1,k): t = cur.next cur.next = t.next t.next = pre.next pre.next = t pre = cur num -= k return dummy.next解法2： 迭代法：两个函数，一个函数分组，一个函数反转结点 遍历链表，并计数，如果是k的倍数就进入反转函数，函数传入pre和cur->next 此时cur和next不等继续循环 此时cur和next相等停止循环 返回last为pre 注意此时 cur = pre->next;
c++：
/** * 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) { if(!head || k == 1) return head; ListNode dummy(-1); dummy.next = head; ListNode* pre = &dummy; ListNode* cur = head; for(int i = 1; cur; i++){ if(i % k == 0){ pre = reverse(pre, cur->next); cur = pre->next; } else { cur = cur->next; } } return dummy.next; } ListNode* reverse(ListNode* pre, ListNode* next) { ListNode* last = pre->next; ListNode* cur = last->next; while(cur != next){ last->next = cur->next; cur->next = pre->next; pre->next = cur; cur = last->next; } return last; } };java：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseKGroup(ListNode head, int k) { if(head == null || k == 1) return head; ListNode dummy = new ListNode(-1); dummy.next = head; ListNode pre = dummy; ListNode cur = head; for(int i = 1; cur != null; i++){ if(i % k == 0){ pre = reverse(pre, cur.next); cur = pre.next; } else { cur = cur.next; } } return dummy.next; } ListNode reverse(ListNode pre, ListNode next) { ListNode last = pre.next; ListNode cur = last.next; while(cur != next){ last.next = cur.next; cur.next = pre.next; pre.next = cur; cur = last.next; } return last; } }python:
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def reverseKGroup(self, head, k): """ :type head: ListNode :type k: int :rtype: ListNode """ if not head or k == 1: return head dummy = ListNode(-1) dummy.next = head pre = dummy cur = head i = 1 while cur: if i % k == 0: pre = self.reverse(pre, cur.next) cur = pre.next else: cur = cur.next i += 1 return dummy.next def reverse(self, pre, next): last = pre.next cur = last.next while cur != next: last.next = cur.next cur.next = pre.next pre.next = cur cur = last.next return last解法3： 递归法 递归基：如果当前节点少于k个，不用反转，直接返回head 首先反转前k个节点，然后返回反转后的头结点new_head,原先的head节点变为反转后的末节点 然后将剩余节点递归求解并与head相连 反转的函数 不需要头结点 直接传入要反转的第一个节点和最后一个节点的下一个节点 注意该反转方法与前两种解法不同 此时head与tail相等 结束循环 返回反转后的第一个节点pre 返回主函数 继续递归求解接下来的节点发现少于k个，不必反转
c++:
/** * 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 *cur = head; for (int i = 0; i < k; ++i) { if (!cur) return head; cur = cur->next; } ListNode *new_head = reverse(head, cur); head->next = reverseKGroup(cur, k); return new_head; } ListNode* reverse(ListNode* head, ListNode* tail) { ListNode* pre = tail; while(head != tail){ ListNode* t = head->next; head->next = pre; pre = head; head = t; } return pre; } };java:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode cur = head; for (int i = 0; i < k; ++i) { if (cur == null) return head; cur = cur.next; } ListNode new_head = reverse(head, cur); head.next = reverseKGroup(cur, k); return new_head; } public ListNode reverse(ListNode head, ListNode tail) { ListNode pre = tail; while(head != tail){ ListNode t = head.next; head.next = pre; pre = head; head = t; } return pre; } }python:
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def reverseKGroup(self, head, k): """ :type head: ListNode :type k: int :rtype: ListNode """ cur = head for i in xrange(k): if not cur: return head cur = cur.next new_head = self.reverse(head, cur) head.next = self.reverseKGroup(cur, k) return new_head def reverse(self, head, tail): pre = tail while head != tail: t = head.next head.next = pre pre = head head = t return pre