示例:
给定这个链表:1->2->3->4->5 当 k = 2 时,应当返回: 2->1->4->3->5 当 k = 3 时,应当返回: 3->2->1->4->5
解析1:K个一组的压栈
代码:
public ListNode reverseKGroup(ListNode head, int k) { Deque<ListNode> stack = new ArrayDeque<ListNode>();//节点栈 ListNode dummy = new ListNode(0);//哑节点 ListNode p = dummy; while (true) {//只要不break就执行,即遇到结束或者是剩单个节点 int count = 0; ListNode tmp = head; while (tmp != null && count < k) {//k若是2 stack.add(tmp); tmp = tmp.next;//1 2 3 4 5到3 count++; } if (count != k) { p.next = head; break; } while (!stack.isEmpty()){ p.next = stack.pollLast();//0指向2 p = p.next;//p变到2 } p.next = tmp; head = tmp; } return dummy.next; }
解析2:递归。开始拿出k个并反转,设置递归出口,进行递归(功能,完成第一组后面的k个一组反转),再进行拼接
作者:老刘 链接:https://www.zhihu.com/question/339135205/answer/794671353 //k个为一组逆序 public ListNode reverseKGroup(ListNode head, int k) { ListNode temp = head; for (int i = 1; i < k && temp != null; i++) { temp = temp.next; } //判断节点的数量是否能够凑成一组 if(temp == null) return head; ListNode t2 = temp.next; temp.next = null; //把当前的组进行逆序 ListNode newHead = reverseList(head); //把之后的节点进行分组逆序 ListNode newTemp = reverseKGroup(t2, k); // 把两部分连接起来 head.next = newTemp; return newHead; } //逆序单链表 private static ListNode reverseList(ListNode head) { if(head == null || head.next == null) return head; ListNode result = reverseList(head.next); head.next.next = head; head.next = null; return result; }