首页 > 代码库 > Leetcode: Rotate List

Leetcode: Rotate List

2024-07-09 06:22:40   212人阅读

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.

Anaylisis: Linked List题目的做法其实比较固定，就是Runner Technique(Two pointer) 方法加上 Dummy Node(设置一个head之前的虚假节点)两种方法，这道题就这样搞一搞就出来了。

需要注意的是：处理null 输入需要特别考虑，然后，需要找到新的linked list的头

 1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13     public ListNode rotateRight(ListNode head, int n) {14         if (head == null || n == 0) return head;15         ListNode prev = new ListNode(-1);16         prev.next = head;17         int size = 0;18         ListNode current = prev;19         ListNode runner = prev;20         while (current.next != null) {21             current = current.next;22             ++size;23         }24         current = prev;25         int shift = n % size;26         for (; shift > 0; shift--) {27             runner = runner.next;28         }29         while (runner.next != null) {30             runner = runner.next;31             current = current.next;32         }33         runner.next = prev.next;34         ListNode newhead = current.next;35         current.next = null;36         return newhead;37     }38 }

 


联系
我们