Java算法——8把链表以K个结点为一组进行翻转

题目描述

K链表翻转是指把每K个相邻的结点看成一组进行翻转，如果剩余结点不足K个，则保持不变。假设给定链表1→2→3→4→5→6→7和一个数K，如果K的值为2，那么翻转后的链表为2→1→4→3→6→5→7。如果K的值为3，那么翻转后的链表为3→2→1→6→5→4→7.

解题思路

首先把前K个结点看成一个子链表，将其进行翻转，把翻转后的子链表链接到头结点后面，然后把接下来的K个结点看成另外一个单独的链表进行翻转，把翻转后的子链表链接到上一个已经完成翻转的子链表的后面。当K=3时：

class LNode {
    /**
     * 数据域
     */
    int data;
    /**
     * 下一个结点的引用
     */
    LNode next;
}

public class Test8 {
    private static LNode reverse(LNode head){
        /**
         * @Author: JavaRecord
         * @Description:把不带头结点的单链表进行翻转
         * @Param [head]
         * @Return linked.list1.LNode
         * @Date 2020/8/19
         * @Time 13:44
         */
        if(head==null||head.next==null){
            return head;
        }
        //前驱结点
        LNode pre=head;
        //当前结点
        LNode cur=head.next;
        //后继结点
        LNode next=cur.next;
        pre.next=null;

        //使当前遍历到的结点cur指向其前驱结点
        while (cur!=null){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }

    public static void reverseK(LNode head,int k){
        /**
         * @Author: JavaRecord
         * @Description:对链表K翻转
         * @Param [head, K]
         * @Return void
         * @Date 2020/8/19
         * @Time 13:49
         */
        if(head==null||head.next==null||k<2){
            return;
        }
        int i=1;
        LNode pre=head;
        LNode begin=head.next;
        LNode end=null;
        LNode pNext=null;
        while (begin!=null){
            //对应图中第（1）步，找到从begin开始第K个结点
            end=begin;
            for(;i<k;i++){
                if(end.next!=null){
                    end=end.next;
                }else{//剩余结点个数小于k
                    return;
                }
            }
            pNext=end.next;             //(2)
            end.next=null;              //(3)
            pre.next=reverse(begin);    //(4)(5)
            begin.next=pNext;           //(6)
            pre=begin;                  //(7)
            begin=pNext;                //(8)
            i=1;
        }
    }

    public static void main(String[] args){
        int i = 1;
        LNode head = new LNode();
        head.next = null;
        LNode tmp = null;
        LNode cur = head;
        for(;i<8;i++){
            tmp = new LNode();
            tmp.data = i;
            tmp.next = null;
            cur.next = tmp;
            cur = tmp;
        }
        System.out.print("顺序输出：");
        for(cur=head.next;cur!=null;cur=cur.next){
            System.out.print(cur.data+" ");
        }
        reverseK(head,3);
        System.out.print("\n逆序输出：");
        for(cur=head.next;cur!=null;cur=cur.next){
            System.out.print(cur.data+" ");
        }
    }
}

程序运行结果：

顺序输出：1 2 3 4 5 6 7 
逆序输出：3 2 1 6 5 4 7 

算法性能分析

只对链表遍历一次，时间复杂度为O(n)；只需要几个指针变量来保存结点的地址信息，空间复杂度为O(1)