首页 > 代码库 > LeetCode: Rotate List 解题报告

LeetCode: Rotate List 解题报告

2024-08-05 06:05:44   218人阅读

Rotate List

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.

SOLUTION 1:

重点就是，要先变成循环链表，end.next = head;再执行ListNode headNew = pre.next; 否则，当n = 0的时候，会返回一个null指针，因为pre是在最后的。

Rotate的精髓是旋转，也就是说当n=0的时候，应该什么也不做，那么pre的下一个应该是头节点。所以我们应该把end.next = head;

另外的做法，就是把n = 0单独拿出来，当n = 0 直接returen head. 这样子就不用考虑这种特殊情况了。pre.next就一定不会是null.

 1 public ListNode rotateRight1(ListNode head, int n) { 2         if (head == null) { 3             return head; 4         } 5          6         int len = getLen(head); 7          8         // 不需要重复地rotate. 9         n = n % len;10         11         ListNode end = head;12         while (n > 0) {13             end = end.next;14             n--;15         }16         17         ListNode pre = head;18         while (end.next != null) {19             pre = pre.next;20             end = end.next;21         }22         23         // 这一句很重要，变成循环链表后，可以处理n = 0的情况。因为尾节点的下一个节点是头节点24         end.next = head;25         ListNode headNew = pre.next;26         pre.next = null;27         28         return headNew;29     }30     31     public int getLen(ListNode head) {32         int len = 0;33         while (head != null) {34             len++;35             head = head.next;36         }37         return len;38     }

 

LeetCode: Rotate List 解题报告


联系
我们