LeetCode-旋转链表问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode-旋转链表问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.旋转链表

题目描述：

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
LeetCode-旋转链表问题,leetcode,链表,算法
思路： 这里向右移动k个位置，相当于从链表的倒数第k个节点处断开，之后再将断开的两个子链表按照相反顺序链接。断开倒数第k个节点需要倒数第k+1个节点地址，链接两个子链表需要最后一个节点地址，返回最终的链表需要倒数第k个节点地址，这样就知道了需要求的东西。倒数第k个节点地址和第k+1个节点的地址可以通过之前学习过的求倒数节点的函数得到，至于最后一个节点地址遍历链表即可得到。不过这里得注意一点，那就是k是链表长度的倍数时，要直接返回链表，不然传入findNode函数的k为0时代码就会出问题。

代码：文章来源地址https://www.toymoban.com/news/detail-759065.html

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head==null) {
            return null;
        }
        int len=0;
        ListNode temp=head;
        while(temp!=null) {
            temp=temp.next;
            len++;
        } 
        if(k%len==0) {
            return head;
        }
        ListNode pre=findNode(head,k%len+1);
        ListNode cur=findNode(head,k%len);
        ListNode tail=findNode(head,1);
        pre.next=null;
        tail.next=head;
        return cur;
    }


    public ListNode findNode(ListNode head, int k) {
        if(head==null) {
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(k!=1) {
            fast=fast.next;
            k--;
        }
        while(fast.next!=null) {
            fast=fast.next;
            slow=slow.next;

        }
        return slow;
    }
}