asp网站开发实验报告,网站建设中应该注意什么,电商网页,郑州网络推广技术K 个一组翻转链表 给你链表的头节点 head #xff0c;每 k 个节点一组进行翻转#xff0c;请你返回修改后的链表。 k 是一个正整数#xff0c;它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍#xff0c;那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改…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 i0; ik; 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];
}
