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
.A: 这里,我们考虑了 n > listLength的情况,
思想:取下后面的拿k个(或者说k%numNode个)链接,然后再把两个接起来即可。
public class Solution { public ListNode rotateRight(ListNode head, int k) { if(head == null) return head; ListNode header = new ListNode(0); header.next = head; int count = 0; ListNode tail = header; while(tail.next!= null){ count++; tail = tail.next; } k = k % count; ListNode runner=header; for(int i =0; i<count-k;i++) runner = runner.next; tail.next = header.next; header.next = runner.next; runner.next = null; return header.next; } }
Mistakes:
----------第二遍,没有考虑 k > number of node 的问题,因此,没有去做mod运算。
-----------------------------------------3rd pass----------------------------------
由于我们直接用tail 指针。然后每次取下第一个节点
取下一个点的时候,有可能就是取下来的tail节点, 这样, 就丢掉这个node了。
解决方法很简单。 就是开始的时候,检测给定的list,是否就一个节点。即可。
public class Solution { public ListNode rotateRight(ListNode head, int k) { if(head == null || head.next == null) // insure tail != head return head; ListNode header = new ListNode(0); header.next = head; // get length of the list. ListNode tail = header; int nNodes = 0; while(tail.next != null){ nNodes ++; tail = tail.next; } k = k % nNodes; // delete each node and add to the tail for(int i =0;i<nNodes - k;i++){ ListNode tmp = header.next; header.next = header.next.next; tail.next = tmp; tail = tail.next; tail.next = null; } return header.next; } }
Learned:
No comments:
Post a Comment