旋转链表面试官你确定要让手写这个吗

94次阅读

共计 3617 个字符，预计需要花费 10 分钟才能阅读完成。

前言：

今天练习了一道关于单链表的算法题《旋转链表》，由于之前写过一篇《单链表反转？面试官你确定要问这个吗？》的文章，然后今天又碰到了这道有关单链表的算法，就想着再 “水篇文章” 吧（带引号的哈），可以证明我没偷懒，按时 写作业 了。嘿嘿 . . . . . . . . .

接下来，①、首先回忆下单链表的数据结构；②、详解描述下什么是旋转链表（题目描述）；③、图解旋转链表代码

数据结构：

1. 单链表的数据结构：

单链表是一种线性结构，它是由一个个 节点（Node） 组成的。并且每个节点（Node）是由一块 数据域（data） 和一块 指针域（next） 组成的。

①、节点（Node）结构图如下：

  1. 节点的数据域 ：data 数据域一般就是用来存放数据的。（注：data 域需要指定类型，只能存放指定类型的数据，不能什么东西都放，是不是呀；那代码中是怎么实现的呢？使用 泛型。）
  2. 节点的指针域 ：next 指针域一般就是存放的指向下一个节点的指针；这个指针其实是一个内存地址，因为 Node 节点对象是存放在 JVM 中的堆内存中，所以节点的 next 指针域中存放就是下一个节点在堆内存中的地址；而在代码中对象的内存地址是赋值给其引用变量了，所以 指针域中存放的是下一个节点对象的引用变量。

②、单链表结构图如下：（下图是由三个节点构成的单链表）

若有所思，en en en . . . . . . 好像单链表的知识在脑海中清晰了些呀；那要不我们快马加鞭，赶紧把单链表的数据结构代码弄出来，然后再思索下怎么 实现旋转操作，en en en. . . .. . . 嘿嘿！

2. 节点类 Node 代码：

创建 Node 节点类，节点类中并且额外提供了两个方法（单链表的创建方法、单链表的遍历打印方法）；

注意：单链表的创建方法 createLinkedList()：Node 节点的插入方式为 尾插法 ，其实还有 头插法 方式；

扩展：链表中节点的插入方式还在 HashMap 中使用到了，在 JDK 1.7 时是头插法，JDK 1.8 时是尾插法；

/**
 * @PACKAGE_NAME: com.lyl.linklist
 * @ClassName: Node
 * @Description:  单链表的 节点类
 * @Date: 2020-06-07 15:51
 **/
public class Node<T> {

    // 节点的数据域
    public T data;
    // 节点的指针域
    public Node next;

    /**
     * 构造方法
     * @param data 数据域值
     */
    public Node(T data) {this.data = data;}


    /**
     * 创建 单链表（尾插法）* @return  返回头结点
     */
    public static Node createLinkedList(){
        // 头节点
        Node<String> head;

        Node<String> n = new Node<String>("111");
        Node<String> n1 = new Node<String>("222");
        Node<String> n2 = new Node<String>("333");
        Node<String> n3 = new Node<String>("444");
        Node<String> n4 = new Node<String>("555");
        Node<String> n5 = new Node<String>("666");
        // 指定头节点
        head = n;
        n.next = n1;
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        // 返回头结点
        return head;
    }


    /**
     * 遍历单链表并在控制台打印输出
     * @param head  单链表的 头结点
     */
    public static void traverse(Node head) {while (head != null) {System.out.print(head.data + "-->");
            head = head.next;
        }
        System.out.print("null");
        System.out.println();}

}

题目描述：

给定一个链表，旋转链表，将链表每个节点 向右移动 k 个位置，其中 k 是非负数。

自我理解：其实是将从尾部数的 k 个节点截取出来再拼接到 head 头节点上。

注意：旋转链表操作会存在两种情况的，正如下面的 实例 1 和 实例 2 。

实例 1：（移动位置 k 小于 单链表的长度）

输入: 1->2->3->4->5->NULL , k = 2（每个节点向右移动 2 个位置）
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

如图：（直接将 4、5 节点截取下来拼接到头结点上）

实例 2：（移动位置 k 大于 单链表的长度）

输入: 0->1->2->NULL , k = 4（每个节点向右移动 4 个位置）
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

如图：

图解代码：

旋转链表使用的方法是 双指针法 ，会存在两个指针：current 指针、previous 指针。通过两个指针移动，并且保证两个指针之间的间距为 需要移动的位置数。

1. 先看图：

2. 代码：

注意：代码中使用的节点类 Node 在本文的上面已经提供了。

/**
 * @PACKAGE_NAME: com.lyl.linklist
 * @ClassName: RotateLinkedListByDoublePointer
 * @Description:  通过双指针法 旋转链表
 * @Date: 2020-06-07 16:00
 **/
public class RotateLinkedListByDoublePointer {

    /**
     *  旋转单链表
     * @param head   单链表 头结点
     * @param placeNum  向右移动的位置数
     */
    public static Node rotate(Node head, int placeNum){if (head == null)
            return null;
        // 临时节点
        Node temp;
        // 将临时节点指向头结点
        temp = head;
        // 记录单链表的长度
        int length = 1;
        // 遍历单链表得到其长度
        while (temp.next != null){
            length++;
            temp = temp.next;
        }
        /**
         *  如果单链表的长度小于移动的位置数
         * (注意：移动位置数是单链表长度的整数倍时，其实相当于单链表没有移动，还是原来的样式)
         */
        if (length <= placeNum){
            // 获取余数，也就是最终要向右移动的位置数
            placeNum = placeNum % length;
        }
        // 如果余数为 0，和上面所说的单链表其实没有变化的
        if (placeNum == 0){return head;}

        // 当前节点指针
        Node current;
        // 前节点指针
        Node previous;
        current = head;
        previous = head;

        // 记录当前指针是否移动了(要求移动的位置数)
        int i = 0;
        while (current.next != null){
            /**
             * 在当前指针移动了 (要求的位置数) 后，并且当前指针还未移动到单链表的尾节点的话，* 此时需要 current、previous 指针一起移动了
             */
            if (i == placeNum){
                current = current.next;
                previous = previous.next;
            }else {// 在当前指针还未移动 (要求的位置数) 前，只有当前指针移动，previous 指针不动
                i++;
                current = current.next;
            }
        }

        /**
         * 当 current 指针移动到了链表的尾部后，此时指针移动结束，将当前 previous、current 指针截取的
         * 这段节点拼接到头节点前，并将 previous 指针指向的节点与后继结点断开连接
         */
        Node newTemp = previous.next;
        previous.next = null;
        current.next = head;

        return newTemp;
    }

    // Test
    public static void main(String[] args) {
        // 创建单链表
        Node head = Node.createLinkedList();
        System.out.print("新创建的单链表：");
        // 遍历新创建的单链表
        Node.traverse(head);
        // 旋转链表，向右移动 10 个位置数
        Node newHead = rotate(head, 10);
        System.out.print("反转后的单链表：");
        // 遍历反转后的单链表
        Node.traverse(newHead);
    }

}

❤不要忘记留下你学习的足迹 [点赞 + 收藏 + 评论]嘿嘿ヾ

一切看文章不点赞都是“耍流氓”，嘿嘿ヾ (◍°∇°◍)ﾉﾞ！开个玩笑，动一动你的小手，点赞就完事了，你每个人出一份力量(点赞 + 评论) 就会让更多的学习者加入进来！非常感谢！~ω~=

正文完
算法-数据结构
发表至： 算法-数据结构
2020-06-07
 0
关于算法-数据结构:PAT甲级1147-Heaps
关于算法-数据结构:PAT甲级1054-The-Dominant-Color
关于算法-数据结构:PAT甲级2020年春季考试-72-The-Judger
关于算法-数据结构:PAT甲级1078-Hashing