2017-04-18 16:03:49 +0000   |     algorithm leetcode linked list two pointers   |   Viewed times   |    

题目

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.

先就算NodeList长度,然后计算出断点位置

假设有1->2->3->4->5,转动12次。先遍历一遍到尾部,计算出List长度为5。然后断点的位置就是,因为k超过list的长度会转回原来的位置。

size - 1 - (k % len)

LinkedList复杂度本来应该是。因为可以直接获得size,直接算出断点,直接嫁接。但题目定死了要用最简陋的单向链表,所以计算长度必须遍历链表到末尾节点,复杂度为

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) { return head; }
        ListNode tail = head;
        int size = 1;
        while (tail.next != null) {
            tail = tail.next;
            size++;
        } // stop at the last element, get the size of list
        int breakPoint = (size - 1 - k) % size;
        if (breakPoint < 0) { breakPoint += size; }
        if (breakPoint != (size - 1)) { // when true, keep the same list
            ListNode newTail = head;
            for (int i = 0; i < breakPoint; i++) { // stop at the breaking point
                newTail = newTail.next;
            }
            tail.next = head;
            head = newTail.next;
            newTail.next = null;
        }
        return head;
    }
}

结果

rotate-list-1