关于java:LeetCode061旋转链表

43次阅读

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

题目形容：给你一个链表的头节点 head，旋转链表，将链表每个节点向右挪动 k 个地位。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：双指针法

首先，如果 head 为 null 或者 head 只有一个节点，间接返回 head；

遍历链表 head 失去链表的长度为 length，依据 k % length 算得 toJump，toJump 为理论须要多少位挪到链表后面，如果 toJump 为 0，阐明旋转后不须要移动，间接返回 head，如果 toJump 大于 0，则初始化 2 个节点 first 和 last 别离指向头结点，而后利用双指针法，失去须要挪的最初几位，具体处理过程如下：

首先将 last 挪动到链表的第 toJump 位；

而后同时挪动 first 和 last 节点，直到 last 的 next 不为空为止。

最初挪动到 last 的 next 为空，此时 last 即为原链表的最初一个节点，first 的 next 节点为新的头结点，此时，初始化 newHead 为 first 的 next 节点，而后将 first 的 next 置空，first 为新链表的最初一个节点，而后将 last 指向原链表的头结点 head，最初返回 newHead 即为旋转后的链表。

public class LeetCode_061 {public static ListNode rotateRight(ListNode head, int k) {if (head == null || head.next == null) {return head;}
        ListNode cur = head;
        // 链表的长度
        int length = 0;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        // 须要将倒数 toJump 位挪到 head 节点后面
        int toJump = k % length;
        if (toJump == 0) {return head;}
        ListNode first = head, last = head;
        while (toJump > 0) {
            last = last.next;
            toJump--;
        }
        while (last.next != null) {
            first = first.next;
            last = last.next;
        }
        ListNode newHead = first.next;
        first.next = null;
        last.next = head;
        return newHead;
    }

    public static void main(String[] args) {ListNode head = new ListNode(0);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);

        ListNode listNode = rotateRight(head, 4);
        while (listNode != null) {System.out.print(listNode.val + " ");
            listNode = listNode.next;
        }
    }
}