链表算法面试题---旋转链表

阅读量：2496 次

发布时间：2019-05-11

本文共 5059 字，大约阅读时间需要 16 分钟。

题目描述

给你一个链表的头节点，和一个值k，请把链表的每个节点向右移动k个位置。

示例1：

链表 1—2---3—4---5，k为2，向右移动1个位置，链表变为：5—1---2—3---4，再移动1个位置，链表变为：4—5---1—2---3

示例2：

链表 1—2---3，k为4，向右移动1个位置，链表变为：3—1---2，移动2个位置，链表变为：2—3---1，移动3个位置，链表变为：1—2---3，

移动4个位置，链表变为：3—1---2

链表的问题，解法总是非常多，反正就是绕来绕去，最后能正确链上就可以了

解法1：

通过遍历k次，每一次遍历都完成一次尾节点的右移，最终实现题目要求

public ListNode revolve1(ListNode head, int k) {
           //边界处理        if (head == null || head.next == null) {
               return head;        }        //如果链表只有两个节点，那么偶数次旋转，实际上链表等于没变，奇数次旋转，则两个节点交换下即可        if (head.next.next == null) {
               if ((k & 1) != 0) {
                   ListNode pre = head;                head = head.next;                head.next = pre;                pre.next = null;            }            return head;        }        for (int i = 0; i < k; i++) {
               //每一次遍历先找到尾节点和尾节点的前一个节点            ListNode tail = head;            ListNode tailPre = null;            while (tail.next != null && tail.next.next != null) {
                   tailPre = tail.next;                tail = tail.next.next;            }            //尾节点的下一个节点指向头节点，尾节点的前一个节点指向null，头节点指向尾节点（此时的尾节点实际上已经是新的头节点了）            //（此处处理过程可以看图解）            tail.next = head;            tailPre.next = null;            head = tail;        }        return head;    }

在这里插入图片描述

tail.next = head;

tailPre.next = null;

在这里插入图片描述

head = tail;

解法2：

通过旋转链表的方式，让原本逆向的操作变成正向的操作，然后就可以从头节点开始直接操作即可。

public ListNode revolve2(ListNode head, int k) {
           if (head == null || head.next == null) {
               return head;        }        //反转链表        ListNode pre = null;        ListNode cur = head;        while (cur != null) {
               ListNode next = cur.next;            cur.next = pre;            pre = cur;            cur = next;        }        //记录旋转之前链表的头节点        ListNode originalHead = head;        //现在我们可以正向的遍历链表，然后把每一个头节点，都移动到直接的头节点后面        //（此处处理过程可以看图解）        for (int i = 0; i < k; i++) {
               ListNode next = pre.next;            originalHead.next = pre;            pre.next = null;            originalHead = pre;            pre = next;        }        //最后再反转回来即可        ListNode pre2 = null;        ListNode cur2 = pre;        while (cur2 != null) {
               ListNode next = cur2.next;            cur2.next = pre2;            pre2 = cur2;            cur2 = next;        }        return pre2;    }

ListNode next = pre.next;

originalHead.next = pre;

pre.next = null;

originalHead = pre;

pre = next;

在这里插入图片描述

第二次遍历：

ListNode next = pre.next;

在这里插入图片描述

解法3：

快慢指针的方式，这种方式也可以经常用来解决需要反向操作链表的问题。

主要思想是，让快指针先走k次，然后慢指针再和快指针一起走，当快指针走完时，慢指针会刚好来到k的位置。此时慢指针的下一个节点就是新的头节点，慢指针当前的节点就是尾节点，最后把快指针当前的节点链上原来的头节点即可。

public ListNode revolve3(ListNode head, int k) {
           //边界处理        if (k == 0 || head == null || head.next == null) {
               return head;        }        //一个快指针，一个慢指针        ListNode fast = head;        ListNode slow = head;        //记录链表的长度        int len = 0;        while (len < k && fast != null) {
               len++;            fast = fast.next;        }        /**         * 如果fast为null，则代表k的值大于链表的长度         * 那么实际上：当k值大于链表的长度时，旋转k次的结果等于旋转（k%链表的长度）次         * 比如：链表为： 1---2---3，k为：4         * k的长度要大于链表的长度，所以k=4%3，k=1，即整个链表实际上只需要旋转一次即可         */        if (fast == null) {
               k = k % len;            //如果k==0，则实际上不用旋转，直接返回即可            if (k == 0) {
                   return head;            }            //否则快指针从头开始，重新先走k次，此时的k已经是和len取模的结果了            fast = head;            for (int i = 0; i < k; i++) {
                   fast = fast.next;            }        }        //此时，慢指针和快指针继续同时走        while (fast != null && fast.next != null) {
               fast = fast.next;            slow = slow.next;        }        //（此处处理过程可以看图解）        //当快指针走到底时，此时慢指针的下一个节点就是新的头节点        ListNode newHead = slow.next;        //慢指针当前节点就是尾节点        slow.next = null;        //快指针的下一节点（就是原来链表的最后一个节点）链上原来的头节点即可        fast.next = head;        //最后返回新的头节点        return newHead;    }

在这里插入图片描述

ListNode newHead = slow.next;

在这里插入图片描述

slow.next = null;

在这里插入图片描述

fast.next = head;

在这里插入图片描述

解法4：

比较正常的思路，先遍历一次链表，得到链表的长度，和链表的最后一个节点，有了链表的长度就可以直接遍历到（长度-k）的位置了，之后直接拼接下即可。

public ListNode revolve4(ListNode head, int k) {
           if (head == null || head.next == null) {
               return head;        }        //计算链表的长度，顺便得到链表的最后一个节点        ListNode cur = head;        int len = 1;        while (cur.next != null) {
               len++;            cur = cur.next;        }        //和第三种解法一样，对于k超过链表长度的问题，直接取模即可        int index = len - (k % len) - 1;		//（此处处理过程可以看图解）        //最后一个节点指向头节点，此时链表是一个环        cur.next = head;        //来到重新组装链表的位置        for (int i = 0; i < index; i++) {
               head = head.next;        }        //head的next节点便是新的头节点，head自身便是尾节点        ListNode newHead = head.next;        //断开头尾节点        head.next = null;        return newHead;    }

在这里插入图片描述