引言
题目链接：https://leetcode.com/problems/reverse-nodes-in-k-group/
题目大意
给定一个链表，一次反转链表的k个节点（每k个节点翻转一次），最后返回修改后的列表。
Hint：k是正整数，并且小于或等于链表的长度。如果节点数不是k的倍数，那么最后的剩余节点应该保持不变。
- Example
|
1 2 3 |
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 |
题解
一句话题解：这题算是24题Swap Nodes in Pairs的进阶版本。使用快慢指针，先行指针先走k步，就地转置慢指针与快指针之间的节点，最后处理整个翻转链，重复这个过程直至结束
复杂度
时间复杂度 O(kn)，k是需要翻转的区间长度
空间复杂度 O(1)
AC代码
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 44 45 46 47 48 49 50 51 52 53 54 55 56 |
/** * 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 *ret = new ListNode(-1); ret->next = head; ListNode *fast = ret; ListNode *slow = ret; ListNode *tmp1, *tmp2; while (nullptr != fast && nullptr != fast->next) { int n = k; while (n && nullptr != fast->next) { fast = fast->next; --n; } if (n > 0) { break; } tmp1 = fast->next; tmp2 = slow->next; reverseIntervalList(slow->next, fast); slow->next->next = tmp1; slow->next = fast; slow = fast = tmp2; } return ret->next; } private: void reverseIntervalList(ListNode *begin, ListNode *end) { ListNode *pre = begin; ListNode *cur = begin->next; ListNode *tmp; while (pre != end) { tmp = cur->next; cur->next = pre; pre = cur; cur = tmp; } } }; |
go版本
|
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 |
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func reverseIntervalList(begin, end *ListNode) { pre, cur := begin, begin.Next var tmp *ListNode for pre != end { tmp = cur.Next cur.Next = pre pre = cur cur = tmp } } func reverseKGroup(head *ListNode, k int) *ListNode { ret := &ListNode{-1, nil} ret.Next = head fast, slow := ret, ret var tmp1, tmp2 *ListNode for nil != fast && nil != fast.Next { n := k for n > 0 && nil != fast.Next { fast = fast.Next n-- } if n > 0 { break } tmp1 = fast.Next tmp2 = slow.Next reverseIntervalList(slow.Next, fast) slow.Next.Next = tmp1 slow.Next = fast slow, fast = tmp2, tmp2 } return ret.Next } |
