首页 > 代码库 > [LeetCode系列] K节点倒序问题迭代解法
[LeetCode系列] K节点倒序问题迭代解法
给定链表和整数k, 使用in-space方法将链表按k个为一组进行倒序, 如果剩余个数不足k个则保留其原始顺序.
如给定1->2->3->4->5, k = 2, 需要返回 2->1->4->3->5; 给定1->2->3->4->5, k = 3, 需要返回 3->2->1->4->5.
算法描述:
- 使用指针cur遍历链表;
- 使用指针pilot探索链表, 如果剩余个数不够, 跳出循环, 算法结束; 如果个数足够, 则进行下一步;
- 只要指针cur和pilot没有相遇, 就依次交换相邻的node;
- 重新设置cur和pilot, 返回第2步.
需要说明的是第三步交换相邻的node:
我们设需要交换的2个node分别为cur和cur->next, 这里用到2个指针: pre指向cur的前一个节点. 变换过程如下
ListNode *nt = cur->next->next;
nt保存后节点(需要交换的2节点之后的节点)信息.
cur->next->next = pre->next;
把第2个节点指向第1个节点(新方向).
pre->next = cur->next;
把前节点(需要交换的2节点之前的节点)指向第2个节点(重新构造开头).
cur->next = nt;
把第1个节点指向后节点(重新构造结尾).
整理后, 两个橘黄色节点已经对调, 并且两者前后节点未变.
结束.
代码:
1 class Solution { 2 public: 3 ListNode *reverseKGroup(ListNode *head, int k) { 4 if (head == NULL) return NULL; 5 ListNode *dummy = new ListNode(0); 6 dummy->next = head; 7 ListNode *pre = dummy; 8 ListNode *cur = head; 9 while(cur != NULL) {10 ListNode *pilot = pre->next;11 int remaining = k;12 while (pilot != NULL && remaining-- > 0) pilot = pilot->next;13 if (remaining > 0) break;14 while(cur->next != pilot) {15 ListNode *nt = cur->next->next;16 cur->next->next = pre->next;17 pre->next = cur->next;18 cur->next = nt;19 }20 pre = cur;21 cur = cur->next;22 }23 return dummy->next;24 }25 };
[LeetCode系列] K节点倒序问题迭代解法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。