rotate list java_Rotate List leetcode java

柔情只为你懂 2022-11-03 04:08 120阅读 0赞

题目：

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:

Given 1->2->3->4->5->NULL and k = 2,

return 4->5->1->2->3->NULL.

题解：

这道题主要先理解题意，就是倒着数k个node，从那开始到结尾和之前那部分对调，那个例子就是，4->5拿前面来，1->2->3拿后面去。

几个特殊：

k是可以大于整个list的长度的，所以这时要对k对len取模

如果取模之后得0，相当于不用rotate，直接返回

处理完特殊情况后，就用熟悉的faster/slower双指针解决就好(看到这种linkedlist，倒着数数的，就条件反射了)

先对faster设步长为n，然后faster和slower再一起走，知道faster.next==null，说明slower指向要倒着数的开始点的前一个位置。

所以slow.next就是要返回的newhead，保存一下。

然后把faster.next接到head上，slower.next存为null，作队尾。

这样就把list给rotate了。

这是我想的一种解法，还有一种就是把整个list连起来，变成环，找到切分点断开就行。

解法1：

1    public ListNode rotateRight(ListNode head, int n) \{

2         if(head==null||head.next==null||n==0)

3             return head;

4         ListNode fast = head, slow = head,countlen = head;

5         ListNode newhead = new ListNode(-1);

6         int len = 0;

7

8         while(countlen!=null)\{

9             len++;

10             countlen = countlen.next;

11         \}

12

13         n = n%len;

14         if(n==0)

15             return head;

16

17         for(int i = 0; i

18             fast = fast.next;

19

20         while(fast.next!=null)\{

21             slow = slow.next;

22             fast = fast.next;

23         \}

24

25         newhead = slow.next;

26         fast.next = head;

27         slow.next = null;

28

29         return newhead;

30     \}

解法2：

1 public ListNode rotateRight(ListNode head, int n) \{

2

3     if (head == null || n == 0)

4         return head;

5     ListNode p = head;

6     int len = 1;//since p is already point to head7     while (p.next != null) \{

8         len++;

9         p = p.next;

10     \}

11     p.next = head; //form a loop12     n = n % len;

13     for (int i = 0; i

14         p = p.next;

15     \} //now p points to the prev of the new head16     head = p.next;

17     p.next = null;

18     return head;

19 \}

Reference for 2： http://leetcodenotes.wordpress.com/2013/08/14/leetcode-rotate-list-%E6%8A%8A%E5%90%8Ek%E4%B8%AArotate%E5%88%B0list%E5%89%8D%E9%9D%A2%E5%8E%BB%EF%BC%8Ck%E5%8F%AF%E4%BB%A5%E8%B6%85%E8%BF%87list%E6%9C%AC%E8%BA%AB%E9%95%BF%E5%BA%A6/

发表评论取消回复

表情：

评论列表（有 0 条评论，120人围观）

还没有评论，来说两句吧...

相关阅读

相关 rotate list java_Rotate List leetcode java

题目： Given a list, rotate the list to the right by k places, where k is non-negative. F

柔情只为你懂/ 2022年11月03日 04:08/ 0 赞/ 121 阅读

相关 LeetCode61——Rotate List

LeetCode61——Rotate List 简单的链表操作。维护head和r指针，r初始指向链表末尾，并且r-next=head; 首尾相接，再根据给定K移动特定指针。

Love The Way You Lie/ 2022年08月09日 12:57/ 0 赞/ 145 阅读

相关 Rotate List--LeetCode

题目： Given a list, rotate the list to the right by k places, where k is non-negative.

「爱情、让人受尽委屈。」/ 2022年08月07日 11:56/ 0 赞/ 6 阅读

相关【leetcode每日一题】61.Rotate List

题目： Given a list, rotate the list to the right by k places, where k is non-negative. F

梦里梦外;/ 2022年08月04日 14:37/ 0 赞/ 135 阅读

相关 leetcode 61. Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative. For ex

亦凉/ 2022年07月29日 09:20/ 0 赞/ 181 阅读

相关 LeetCode刷题（C++）——Rotate List（Medium）

Given a list, rotate the list to the right by k places, where k is non-negative. For ex

叁歲伎倆/ 2022年06月16日 11:30/ 0 赞/ 144 阅读

相关 [Leetcode][python]Rotate List/旋转链表

题目大意将一个链表中的元素向右旋转k个位置。解题思路参考：[http://www.cnblogs.com/zuoyuan/p/3785465.html][h

清疚/ 2022年06月07日 06:18/ 0 赞/ 160 阅读

相关【Leetcode】61. Rotate List（链表）

Given a linked list, rotate the list to the right by k places, where kis non-negative.

青旅半醒/ 2022年02月27日 03:58/ 0 赞/ 156 阅读

相关 61. Rotate List

class Solution { public ListNode rotateRight(ListNode head, int k) {

拼搏现实的明天。/ 2021年12月22日 06:51/ 0 赞/ 214 阅读

相关 [LeetCode] Rotate List 旋转链表

Given a list, rotate the list to the right by k places, where k is non-negative. For ex

快来打我*/ 2021年09月19日 10:16/ 0 赞/ 274 阅读