K 个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例：
方法一、模拟法
我们需要把链表节点按照 k 个一组分组，所以可以使用一个指针 head 依次指向每组的头节点。这个指针每次向前移动 k 步，直至链表结尾。对于每个分组，我们先判断它的长度是否大于等于 k。若是，我们就翻转这部分链表，否则不需要翻转。
接下来问题转化为：
1.翻转k个子链表，注意首尾连接
2.巧妙构造头结点，方便操作链表
Swift
//k个一组翻转链表func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {let dummyNode = ListNode(0)dummyNode.next = headvar p:ListNode? = dummyNodevar head = headwhile head != nil {var tail:ListNode? = pfor _ in 0..<k {tail = tail?.nextguard tail != nil else {return dummyNode.next}}let nex = tail?.nextlet result = reverseListNode(head, tail)head = result.0tail = result.1var res = headwhile let result = res {print(result.val)res = result.next}//链接反转后的链表p?.next = headtail?.next = nexp = tailhead = nex}return dummyNode.next}//翻转链表，返回新的头和尾func reverseListNode(_ head:ListNode?, _ tail:ListNode?) -> (ListNode?, ListNode?) {//记录未反转时最后一个元素的下一个，反转后保持链接状态var nextNode = tail?.nextvar p = headwhile nextNode !== tail {let nex = p?.nextp?.next = nextNodenextNode = pp = nex}return (tail, head)}
OC
- (ListNodeOC *)reverseKGroup:(ListNodeOC *)headinteval:(NSInteger)k {//创建哑巴节点ListNodeOC *dummyNode = [[ListNodeOC alloc] initWithVal:0];dummyNode.next = head;ListNodeOC *p = dummyNode;while (head != nil) {ListNodeOC *tail = p;for (NSInteger i=0; i<k; i++) {tail = tail.next;if (!tail) {return dummyNode.next;}}ListNodeOC *pre = tail.next;NSArray *result = [self reverseListNode:head tail:tail];head = result.firstObject;tail = result.lastObject;//链接首尾顺序p.next = head;tail.next = pre;p = tail;head = pre;}return dummyNode.next;
}- (NSArray *)reverseListNode:(ListNodeOC *)head tail:(ListNodeOC *)tail {ListNodeOC *previ = tail.next;ListNodeOC *p = head;while (previ != tail) {ListNodeOC *nex = p.next;p.next = previ;previ = p;p = nex;}return @[tail, head];
}
