首页 > 代码库 > Leetcode25--->Reverse Nodes in k-Group(以k个节点为段，反转单链表)
Leetcode25--->Reverse Nodes in k-Group(以k个节点为段，反转单链表)
题目： 给定一个单链表，一次反转k个节点，最终返回翻转后的链表的头节点；如果链表不足k个，则不变
举例：
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
解题思路：
1. 首先要确定链表的头节点newHead;即如果链表的节点个数大于k,则头节点为第k个节点；否则头节点不变；
2. 区分每一段，即确定段的开始和结尾；当前段的开始start, 段的结尾可以用k确定；下一段的开始为end;
3. 每k个节点之间的反转；
4. 段与段之间的连接，prevNode指向前一段的最后一个节点；
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9 public class Solution {10 public ListNode reverseKGroup(ListNode head, int k) {11 if(head == null || k <= 1)12 return head;13 ListNode begin = head; // begin是当前段的开始14 ListNode end = begin; // end是下一段的开始15 ListNode newHead = begin; // 新的链表头16 ListNode prevNode = head; // 是上一段的最后一个节点17 int flag = 0; // 记录是第几段18 while(end != null){19 int count = 1;20 while(end.next != null && count < k){21 end = end.next;22 count ++;23 }24 if(count == k){25 if(flag == 0){26 newHead = end;27 }28 flag ++;29 if(flag > 1){ // 不是第一段时就需要段与段之间的连接30 prevNode.next = end; // 段和段之间进行连接31 prevNode = begin;32 }33 end = end.next; // 下一个段的开始34 ListNode prev = null;35 int i = 0;36 while(i < k){ // 链表的反转37 ListNode nextNode = begin.next;38 begin.next = prev;39 prev = begin;40 begin = nextNode;41 i++;42 }43 begin = end; // 下一个段的开始44 prevNode.next = end; // 两个段之间连接，是为了避免下一段节点数不足k个，则不能使用第30行代码来连接段45 }46 else47 break;48 }49 return newHead;50 }51 }
Leetcode25--->Reverse Nodes in k-Group(以k个节点为段，反转单链表)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。