1,非递归解决
每k个一组进行反转,如果不够k个就不需要反转,关于链表的反转,不会的可以看下《432,剑指 Offer-反转链表的3种方式》 。最简单的一种方式就是把链表每k个分成一组,然后反转这每一组的节点,接着在把他们串起来即可。
public ListNode reverseKGroup(ListNode head, int k) { //先创建一个哑节点 ListNode dummy = new ListNode(0); //让哑节点的指针指向链表的头 dummy.next = head; //开始反转的前一个节点,比如反转的节点范围是[link1,link2], //那么pre就是link1的前一个节点 ListNode pre = dummy; ListNode end = dummy; while (end.next != null) { //每k个反转,end是每k个链表的最后一个 for (int i = 0; i < k && end != null; i++) end = end.next; //如果end是空,说明不够k个,就不需要反转了,直接退出循环。 if (end == null) break; //反转开始的节点 ListNode start = pre.next; //next是下一次反转的头结点,先把他记录下来 ListNode next = end.next; //因为end是这k个链表的最后一个结点,把它和原来链表断开, //这k个节点我们可以把他们看做一个小的链表,然后反转这个 //小链表 end.next = null; //因为pre是反转链表的前一个节点,我们把小链表[start,end] //反转之后,让pre的指针指向这个反转的小链表 pre.next = reverse(start); //注意经过上一步反转之后,start反转到链表的尾部了,就是已经 //反转之后的尾结点了,让他之前下一次反转的头结点即可(上面分析 //过,next就是下一次反转的头结点) start.next = next; //前面反转完了,要进入下一波了,pre和end都有重新赋值 pre = start; end = start; } return dummy.next; } //链表的反转 private ListNode reverse(ListNode head) { ListNode pre = null; ListNode curr = head; while (curr != null) { ListNode next = curr.next; curr.next = pre; pre = curr; curr = next; } return pre; }
2,递归方式解决
这里并不是反转全部的节点,而是每k个节点进行反转,递归调用,直到不能完全反转为止,如果对于递归不了解的可以先看下《426,什么是递归,通过这篇文章,让你彻底搞懂递归》
看下代码
public ListNode reverseKGroup(ListNode head, int k) { //边界条件判断 if (head == null || head.next == null) return head; ListNode tail = head; for (int i = 0; i < k; i++) { //剩余数量小于k的话,则不需要反转。 if (tail == null) return head; tail = tail.next; } // 反转前 k 个元素 ListNode newHead = reverse(head, tail); //下一轮的开始的地方就是tail head.next = reverseKGroup(tail, k); return newHead; } /* 链表的反转,不是反转全部,只反转区间[head,tail)中间的节点,左闭右开区间 */ private ListNode reverse(ListNode head, ListNode tail) { ListNode pre = null; ListNode next = null; while (head != tail) { next = head.next; head.next = pre; pre = head; head = next; } return pre; }
我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接:https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666