链表每N个节点的子链进行一次翻转（双指针法，每步注释，O(n)时间复杂度 O(1)空间复杂度）

拼搏现实的明天。 2024-03-27 07:31 12阅读 0赞

> 输入输出示范  
> 翻转前 link list：8 7 6 5 4 3 2 1  
> 翻转后 link list：6 7 8 3 4 5 2 1  
> 如果你没有做过链表双指针翻转请先看这篇博客，一步步来学习理解  
> [https://blog.csdn.net/HumorChen99/article/details/128817580][https_blog.csdn.net_HumorChen99_article_details_128817580]

*  翻转流程

> 翻转前 link list：10 9 8 7 6 5 4 3 2 1  
> 执行一次翻转后 link list：8 9 10 7 6 5 4 3 2 1  
> 子链翻转后头结点是：8 尾结点是：10  
> 执行一次翻转后 link list：8 9 10 5 6 7 4 3 2 1  
> 子链翻转后头结点是：5 尾结点是：7  
> 执行一次翻转后 link list：8 9 10 5 6 7 2 3 4 1  
> 子链翻转后头结点是：2 尾结点是：4  
> 翻转后 link list：8 9 10 5 6 7 2 3 4 1

*  代码

/**
     * 每n个翻转一次
     * @author humorchen
     * @date 2023/1/31 15:25
     */
    public class ReverseLinkListEveryPart {
        
        public static void main(String[] args) {
        
            // 产生一个链表
            Node head = LinkListUtil.newList(8);
            // 打印没有翻转之前的
            LinkListUtil.print("翻转前", head);
            // 每n个节点为1组进行翻转，不足n个不翻转
            int n = 3;
            // 翻转后的头节点
            Node reversedList = reverse(head, n);
            // 打印
            LinkListUtil.print("翻转后", reversedList);
        }
    
        /**
         * 每n个节点为1组进行翻转，不足n个不翻转
         * @param head
         * @param n
         * @return
         */
        static Node reverse(Node head, int n) {
        
            // 特殊情况打回
            if (n < 2 || head == null) {
        
                return head;
            }
            // 设当前节点游标为cur,pre是cur的前一个节点，firstHead是第一个子链的头结点，preTail是上一个子链的尾结点
            Node pre = null, cur = head, firstHead = null, preTail = null;
            // 当前节点不为空
            while (cur != null) {
        
                // 向前探查没有n个节点就不执行翻转子链表了
                if (!hasFullNode(cur, n)) {
        
                    break;
                }
                // t来计数翻转n个
                int t = n;
                // subHead是当前被翻转后子链的头节点，subTail是该子链尾结点
                Node subHead = null, subTail = cur;
                // 从cur开始翻转t个节点
                while (cur != null && t > 0) {
        
                    // 提前存储cur的下一个节点，避免丢失让游标无法继续向右前行
                    Node next = cur.next;
                    // cur的下一个节点设置为上一个节点（翻转操作）
                    cur.next = pre;
                    // cur成为pre,cur右移
                    pre = cur;
                    cur = next;
                    // 翻转个数计数
                    --t;
                    // 翻转到了最后一个，记为子链的头
                    if (t == 0) {
        
                        subHead = pre;
                    }
                }
                // 第一个子链没找到的时候，把当前子链头设置为第一子链头
                if (firstHead == null) {
        
                    firstHead = subHead;
                }
                // 上一个子链的尾结点和当前子链头结点链接起来
                if (preTail != null) {
        
                    preTail.next = subHead;
                }
                // 当前子链的尾巴和下一个节点链接起来
                subTail.next = cur;
                // 覆盖上一个子链尾节点
                preTail = subTail;
                LinkListUtil.print("执行一次翻转后", firstHead);
                System.out.println("子链翻转后头结点是：" + (subHead != null ? subHead.val : -1) + " 尾结点是：" + subTail.val);
            }
            // 有翻转过则有第一次翻转子链的头节点firstHead，没有翻转的话直接返回原来的头节点
            return firstHead != null ? firstHead : head;
        }
    
        /**
         * 看当前节点开始数有没有n个节点
         * @param cur
         * @param n
         * @return
         */
        static boolean hasFullNode(Node cur, int n) {
        
            while (cur != null && n > 1) {
        
                cur = cur.next;
                --n;
            }
            return cur != null;
        }
    }

[https_blog.csdn.net_HumorChen99_article_details_128817580]: https://blog.csdn.net/HumorChen99/article/details/128817580